完全背包

背包的问题本质上就是三重循环，一层循环物品，一层循环体积，一层循环决策

for 物品
  for 体积
    for 决策

只不过01背包跟完全背包在第三层循环决策的时候只有2种选择（完全背包是被优化的，01背包是真的只有两种选择）所以不用三重循环。

leetcode 322 找零钱

这道题本质上还是要3重循环来做的，只不过可以进行优化变成两重循环，在了解优化思路之前如果直接看答案肯定会懵。因为我们无法了解到优化是从哪里来的。
dp最核心的思想是要明白你f[i][j] 表达的是什么样的集合。 对于这道题，因为你每个coin能够选择无限多次，那么f[i][j] 实际上就表达的是当前第i个coin在j amount 下面你能够选择最小的数从而凑出j。
那么一开始我们每个dp[i][j]里面都要设置成最大数，只有能够正好找零才更新dp[i][j]。所以初始化的时候，dp[0][j] 只有在coin上面有更新，下面是初始化部分的代码

   int[][] dp = new int[n+1][amount+1];
    for (int i = 0; i <= n; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= amount; j++) {
            for (int k = 0; k * coins[i] <= j; k++) {
                if (dp[0][j - k * coins[i]] != Integer.MAX_VALUE) dp[0][j] = Math.min(dp[0][j], dp[0][j - k *coins[i]] + k);
            }
        }
    }

n就是第几个coin， amount就是你要凑出的数目当amount - k*coins[i] == 0的时候，你就找到一个刚好凑出这个数目的最小数目了。所以dp[0][j] 就是一个包含每个零钱选任意次而能够凑出j这个数目的最小数的集合

初始化过后你就可以从第1个到第n个coin 进行循环，然后每个coin都尝试k次，判断条件就是k*coin 要小于amount并且dp[i-1][j - k * coin] 不是最大数，因为我们初始化过了，所以dp[i-1]就代表最开始零钱能够凑出j的数字。然后记录下来最小值，代码如下

public int coinChange(int[] coins, int amount) {
    if (amount < 1) return 0;
    int n = coins.length;
    int[][] dp = new int[n+1][amount+1];
    for (int i = 0; i <= n; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= amount; j++) {
            for (int k = 0; k * coins[i] <= j; k++) {
                if (j >= coins[i] && dp[0][j - coins[i]] != Integer.MAX_VALUE) dp[0][j] = Math.min(dp[0][j], dp[0][j - coins[i]] + 1);
            }
            // if (j - coins[i] == 0) dp[0][j] = Math.min(dp[0][j], dp[0][j-coins[i]] + 1);
        }
    }
    // System.out.println(Arrays.toString(dp[0]));
    for (int i = 1; i <= n; i++) {
        dp[i][0] = 0;
        for (int j = 0; j <= amount; j++) {
            for (int k = 0; k * coins[i-1] <= j; k++) {
                if (dp[i-1][j - k * coins[i-1]] != Integer.MAX_VALUE) dp[i][j] = Math.min(dp[i-1][j], dp[i][j - k *coins[i-1]] + k);
            }
        }
        // System.out.println(Arrays.toString(dp[i]));
    }
    if (dp[n][amount] == Integer.MAX_VALUE) return -1;
    return dp[n][amount];

优化

明白了底层逻辑后，我们就可以尝试优化了，因为我们第三层循环就是在不断试当前coin取多少次可以凑出j，那么我们在刚开始初始化的时候，已经计算出了当前每个coin能够凑出j的最小值，那么我们在之前算过的基础上在j-coin[i] == 0 的基础上 + 1就好了。下面是简单优化过的版本（这里只优化了时间维度），后面还会有一个空间维度的优化）

    public int coinChange(int[] coins, int amount) {
        if (amount < 1) return 0;
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        for (int i = 0; i <= n; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
        dp[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                // for (int k = 0; k * coins[i] <= j; k++) {
                    if (dp[0][j - coins[i]] != Integer.MAX_VALUE) dp[0][j] = Math.min(dp[0][j], dp[0][j - coins[i]] + 1);
                // }
                // if (j - coins[i] == 0) dp[0][j] = Math.min(dp[0][j], dp[0][j-coins[i]] + 1);
            }
        }
        System.out.println(Arrays.toString(dp[0]));
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 0;
            for (int j = 0; j <= amount; j++) {
                // for (int k = 0; k * coins[i-1] <= j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i-1][j]);
                if (j >= coins[i-1] && dp[i][j - coins[i-1]] != Integer.MAX_VALUE) dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i-1]] + 1);
                // }
            }
            // System.out.println(Arrays.toString(dp[i]));
        }
        if (dp[n][amount] == Integer.MAX_VALUE) return -1;
        return dp[n][amount];
    }

被注释掉的部分就是我们优化的部分，这样也方便你看出我对哪里进行了优化。

空间优化

因为完全背包是基于前面计算过的最小数或者最大数，那么我们就可以把空间压缩成一维。代码如下

    public int coinChange(int[] coins, int amount) {
        if (amount < 1) return 0;
        int n = coins.length;
        int[] dp = new int[amount+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        // for (int i = 0; i < n; i++) {
        //     for (int j = coins[i]; j <= amount; j++) {
        //         // for (int k = 0; k * coins[i] <= j; k++) {
        //             if (dp[0][j - coins[i]] != Integer.MAX_VALUE) dp[0][j] = Math.min(dp[0][j], dp[0][j - coins[i]] + 1);
        //         // }
        //         // if (j - coins[i] == 0) dp[0][j] = Math.min(dp[0][j], dp[0][j-coins[i]] + 1);
        //     }
        // }
        // System.out.println(Arrays.toString(dp[0]));
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= amount; j++) {
                // for (int k = 0; k * coins[i-1] <= j; k++) {
                if (j >= coins[i-1] && dp[j - coins[i-1]] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j - coins[i-1]] + 1);
                // }
            }
            // System.out.println(Arrays.toString(dp[i]));
        }
        if (dp[amount] == Integer.MAX_VALUE) return -1;
        return dp[amount];
    }