动态规划问题， 寻找子问题，自下而上取思考。求dp[i], 就要先求dp[i-1], 看两者是不是有关系。

零钱问题： 求n = 10 , 那么 n = 9 可以先求出， 那么n = 8 可以先求出。然后从下到上取遍历。

背包问题：遍历两次、可以先遍历背包，可以先遍历物品。具体情况具体分析。

先把题目抽象为背包和物品。这里用两个题目举例分析。

for(int i = 1; i< dp.length; i++){ //遍历背包，背包是总金额

for(int j = 0; j< coins.length; j++){ // 遍历物品

if(i>= coins[j] && dp[i - coins[j]] != amount +1){

dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);// 核心。求最小。为什么要加1 ，因为你拿出了一个物品，要加上这个物品的价值。这里是1；

    public int coinChange(int[] coins, int amount) {
        int dp[] = new int[amount+1];
        
        Arrays.fill(dp,amount+1);
        dp[0] = 0;//这里 写1 ，测试不通过
        for(int i = 1; i< dp.length; i++){    //遍历背包，背包是总金额
            for(int j = 0; j< coins.length; j++){ // 遍历物品
                if(i>= coins[j] &&  dp[i - coins[j]] != amount +1){
                    dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
                }
               
            }
        }
        return dp[amount] == amount +1 ? -1 : dp[amount];
    }

和零钱问题1 一样

//背包是 n , 物品是平方数

//这里是求最值，排列数和组合数无关。

//看出每次dp[j]都要选最?的，所以?0下标的dp[i]?

// 定要初始为最?值，这样dp[j]在递推的时候才不会被初始值覆盖。

for(int i = 0; i<= n ; i++){//遍历背包

for(int j = 1; j*j < i ; j++){//遍历物品

dp[i] = Math.min(dp[i], dp[i-j*j] + 1);// 返回背包的结果

解法2， //遍历物品，再遍历背包

for(int i = 1 ; i*i <= n; i++){//遍历物品

for(int j = 1 ; j<= n ; j++){//再遍历背包

if(j - i*i >= 0){

dp[j] = Math.min (dp[j- i*i] + 1, dp[j]);//背包的值

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        //背包是 n , 物品是平方数
        //这里是求最值，排列数和组合数无关。 
        //看出每次dp[j]都要选最?的，所以?0下标的dp[i]?
// 定要初始为最?值，这样dp[j]在递推的时候才不会被初始值覆盖。
        // for(int i = 0; i<= n ; i++){//遍历背包
        //     for(int j = 1; j*j < i ; j++){
        //         dp[i] = Math.min(dp[i], dp[i-j*j] + 1);
        //     }
        // }
        // return dp[n];


        //遍历物品，再遍历背包
        for(int i = 1 ; i*i <= n; i++){
            for(int j = 1 ; j<= n ; j++){//再遍历背包
                if(j - i*i >= 0){
                    dp[j] = Math.min (dp[j- i*i] + 1, dp[j]);  //j, 背包的值
                }
            }
        }
        return dp[n];
    }
}

零钱问题2 ： 求组合数（和排列无关）

求组合数-------先外层for循环遍历物品（coins），内层for遍历背包（amount）

class Solution {
    public int change(int amount, int[] coins) {
        
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        // 先外层for循环遍历物品（coins），内层for遍历背包（amount）
        for(int i = 0; i < coins.length; i++){ // 外层for循环遍历物品
            for(int j = coins[i]; j < amount +1; j++){ // 内层for遍历背包
                dp[j] += dp[j - coins[i]];  // 背包不同大小，自下而上累加
            }
        }
        return dp[amount];
    }
}

你，我加油：P