代码随想录第45天|● 70. 爬楼梯 （进阶） ● 322. 零钱兑换 ● 279.完全平方数

文章目录

• ● 70. 爬楼梯 （进阶）
• • 思路：- 排列 先value后weight
  • 代码：
  • ● 322. 零钱兑换
  • • 思路：
    • 代码
    • ● 279.完全平方数
    • • 思路：
      • 代���

        ● 70. 爬楼梯 （进阶）

        思路：- 排列 先value后weight

        代码：

        import java.util.*;public class Main{    public static void main(String[] args){        Scanner sc = new Scanner(System.in);        int n=sc.nextInt();        int m=sc.nextInt();        int[] dp=new int[n+1];        dp[0]=1;        for(int j=1;j            for(int i=0;i                if(j=i)dp[j]+=dp[j-i];            }        }        System.out.println(dp[n]);            }}     public int coinChange(int[] coins, int amount) {        // int n=coins.length;        int[] dp=new int[amount+1];        dp[0]=0;        for(int i=1;i            dp[i]=Integer.MAX_VALUE/2;// 除 2 是防止下面 + 1 溢出        }        for(int i=0;i            for(int j=coins[i];j                dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);            }        }        return dp[amount]==Integer.MAX_VALUE/2?-1:dp[amount];    }}    public int coinChange(int[] coins, int amount) {        int max = Integer.MAX_VALUE;        int[] dp = new int[amount + 1];        //初始化dp数组为最大值        for (int j = 0; j