完全背包问题（279，322，518）

递推式：dp[i] = Math.min(dp[i], dp[i-j*j]+1);

class Solution {
    public int numSquares(int n) {
        //背包问题
        int[] dp = new int[n+1];//dp[i]表示和为i的最少平方数
        dp[0] = 0;
        for(int i = 1;i <= n;i++){
            dp[i] = n;
            for(int j = 1;j*j <= i;j++)
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
        }
        return dp[n];
    }
}

递推：dp[i][j] = min(dp[i], dp[i][j-coins[i-1]])

class Solution {
    public int coinChange(int[] coins, int amount) {
        //完全背包问题
        // int n = coins.length, max = amount+1;
        // int[][] dp = new int[n+1][max];//dp[i][j]表示前i个硬币组成j的最少硬币数

        // //初始化
        // Arrays.fill(dp[0], max);//max表示无解！
        // dp[0][0] = 0;

        // for(int i = 1;i <= n;i++){
        //     for(int j = 0;j <= amount;j++){
        //         //不加入当前硬币
        //         dp[i][j] = dp[i-1][j];
        //         if(coins[i-1] <= j){//加入当前硬币
        //             dp[i][j] = Math.min(dp[i][j], dp[i][j-coins[i-1]]+1);
        //         }
        //     }
        // }
        // return dp[n][amount] > amount ? -1 : dp[n][amount];

        //答案 动态规划
        //核心思想：f[j] = min{f[j-coins[0], f[j-coins[1], f[j-coins[2], ...]}
        int n = coins.length, max = amount+1;
        int[] dp = new int[max];//dp[j]表示coins组成j所需的最少硬币

        //初始化
        Arrays.fill(dp, max);//max表示无解
        dp[0] = 0;

        for(int j = 0;j <= amount;j++){
            for(int i = 1;i <= n;i++){
                if(coins[i-1] <= j){
                    dp[j] = Math.min(dp[j], dp[j-coins[i-1]]+1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

class Solution {
    public int change(int amount, int[] coins) {
        // int n = coins.length;
        // int[][] dp = new int[n+1][amount+1];//dp[i][j]表示前i个硬币组成j的方案数

        // //初始化
        // Arrays.fill(dp[0], 0);
        // dp[0][0] = 1;//千万不能忽视初始化！！

        // for(int i = 1;i <= n;i++){
        //     for(int j = 0;j <= amount;j++){
        //         //不加入当前硬币
        //         dp[i][j] = dp[i-1][j];
        //         if(coins[i-1] <= j){//加入当前硬币
        //             dp[i][j] = dp[i][j]+dp[i][j-coins[i-1]];
        //         }
        //     }
        // }
        // return dp[n][amount];

        //空间优化
        int[] dp = new int[amount+1];//dp[i][j]表示前i个硬币组成j的方案数

        //初始化
        Arrays.fill(dp, 0);
        dp[0] = 1;//千万不能忽视初始化！！

        for(int coin : coins){
            for(int j = coin;j <= amount;j++){
                    dp[j] += dp[j-coin];
            }
        }
        return dp[amount];
    }
}