零钱兑换,完全背包,一二维dp

linwt · linwt · commit cb720f764434 · 2022-03-19T23:02:41.000+08:00
diff --git a/leetcode_Java/Solution0322.java b/leetcode_Java/Solution0322.java
@@ -41,28 +41,77 @@ private int dfs(int[] memo, int[] coins, int amount) {
 
 
 /*
-动态规划：完全背包，先物品再背包是计算组合，先背包再物品是计算排列，本题物品背包顺序无关，必须正序遍历背包才能重复使用物品
+动态规划：完全背包，二维数组
 1、题目：给你一个整数数组coins，表示不同面额的硬币；以及一个整数amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。你可以认为每种硬币的数量是无限的。
 2、题目简化：求凑成总金额amount所需的最少硬币数
-3、定义dp数组：dp[i] 表示凑成总金额i所需的最少硬币数
-4、状态转移方程：dp[i] = Math.min(dp[i], dp[i-coin]+1); 需要比较多种硬币情况下的最小值
+3、定义dp数组：dp[i][j] 表示使用前i个硬币，凑成总金额j所需的最少硬币数
+4、状态转移方程
+  if (j - coins[i - 1] >= 0)  dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);   // 金额足够，“不用”和“用”两种情况比较出最少
+  else  dp[i][j] = dp[i - 1][j];    // 金额不够，只能选择“不用”该硬币
+  注意：dp[i - 1][j - coins[i - 1]] 表示第i个硬币只用一次，属于0-1背包。dp[i][j - coins[i - 1]] 表示第i个硬币重复使用，属于完全背包。
 5、初始化：
+  1）首列 dp[i][0] 表示使用前i个硬币，凑成总金额j所需的最少硬币数为0
+  2）其他填充一个不可能的硬币数，使得不影响计算，也方便状态转移时取最小值
+6、遍历dp数组填表：第一层遍历硬币，第二层遍历金额，都从1开始，正序遍历。两个for循环先后都可以，因为计算当前状态只需要当前行左边的状态和上一行的状态
+7、返回结果：最后一个状态就是结果
+
+二维dp更新过程，从左到右，从上到下
+coins = [1, 2, 5], amount = 11
+0  12  12  12  12  12  12  12  12  12  12  12
+0  1   2   3   4   5   6   7   8   9   10  11
+0  1   1   2   2   3   3   4   4   5   5   6
+0  1   1   2   2   1   2   2   3   3   2   3
+ */
+class Solution {
+    public int coinChange(int[] coins, int amount) {
+        int n = coins.length;
+        int[][] dp = new int[n + 1][amount + 1];
+        for (int i = 0; i <= n; i++) {
+            for (int j = 1; j <= amount; j++) {
+                dp[i][j] = amount + 1;
+            }
+        }
+        for (int i = 1; i <= n; i++) {
+            for (int j = 1; j <= amount; j++) {
+                if (j - coins[i - 1] >= 0) {
+                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
+                } else {
+                    dp[i][j] = dp[i - 1][j];
+                }
+            }
+        }
+        return (dp[n][amount] == amount + 1) ? -1 : dp[n][amount];
+    }
+}
+
+
+/*
+动态规划：完全背包，一维数组
+1、定义dp数组：dp[i] 表示凑成总金额i所需的最少硬币数
+2、状态转移方程：dp[i] = Math.min(dp[i], dp[i-coin]+1); 需要比较多种硬币情况下的最小值
+3、初始化：
    dp[i]=amount+1; 填充一个不可能的硬币数，使得不影响计算，也方便状态转移时取最小值
    dp[0]=0; 表示凑成总金额0所需的最少硬币数为0，方便后面推导
-6、遍历dp数组填表：第一个for循环遍历dp数组的未知位置，第二个for循环遍历硬币数组，根据条件获取dp数组的已知位置，根据状态转移方程取已知结果汇总计算未知结果
-7、返回结果：最后一个状态就是结果
+4、遍历dp数组填表：
+  1）第一个for循环遍历dp数组的未知位置，第二个for循环遍历硬币数组，根据条件获取dp数组的已知位置，根据状态转移方程取已知结果汇总计算未知结果
+  2）先物品再背包是计算组合，先背包再物品是计算排列，本题物品背包顺序无关，必须正序遍历背包才能重复使用物品
+5、返回结果：最后一个状态就是结果
+
+一维dp更新过程，从左到右
+coins = [1, 2, 5], amount = 11
+0  12  12  12  12  12  12  12  12  12  12  12
+   1   2   3   4   5   6   7   8   9   10  11
+       1   2   2   3   3   4   4   5   5   6
+                   1   2   2   3   3   2   3
  */
 class Solution {
     public int coinChange(int[] coins, int amount) {
         int[] dp = new int[amount + 1];
         Arrays.fill(dp, amount + 1);
         dp[0] = 0;
-        for (int i = 1; i <= amount; i++) {
-            for (int coin : coins) {
-                if (i - coin < 0) {
-                    continue;
-                }
-                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
+        for (int coin : coins) {
+            for (int i = coin; i <= amount; i++) {
+                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
             }
         }
         return (dp[amount] == amount + 1) ? -1 : dp[amount];
@@ -78,9 +127,11 @@ public int coinChange(int[] coins, int amount) {
         int[] dp = new int[amount + 1];
         Arrays.fill(dp, amount + 1);
         dp[0] = 0;
-        for (int coin : coins) {
-            for (int i = coin; i <= amount; i++) {
-                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
+        for (int i = 1; i <= amount; i++) {
+            for (int coin : coins) {
+                if (i - coin >= 0) {
+                    dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
+                }
             }
         }
         return (dp[amount] == amount + 1) ? -1 : dp[amount];
diff --git a/leetcode_Java/Solution0518.java b/leetcode_Java/Solution0518.java
@@ -2,14 +2,67 @@
 
 
 /*
-动态规划：完全背包，先物品再背包是计算组合，先背包再物品是计算排列，必须正序遍历背包才能重复使用物品
+动态规划：完全背包，二维数组
 1、题目：给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。
 2、题目简化：求凑成总金额amount的硬币组合数
-3、定义dp数组：dp[i] 表示凑成总金额i的硬币组合数
-4、状态转移方程：dp[i] += dp[i-coin]，即所有dp[i-coin]相加
-5、初始化：dp[0] = 1，表示凑成总金额0的硬币组合数为1，方便后面推导
-6、遍历dp数组填表：第一个for循环遍历硬币数组，第二个for循环遍历dp数组的未知位置，根据条件获取dp数组的已知位置，根据状态转移方程取已知结果汇总计算未知结果
+3、定义dp数组：dp[i][j] 表示使用前i个硬币，凑成总金额j的硬币组合数
+4、状态转移方程
+  if (j - coins[i - 1] >= 0)  dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];    // 金额足够，“不用”和“用”两种情况相加
+  else  dp[i][j] = dp[i - 1][j];    // 金额不够，只能选择“不用”该硬币
+  注意：dp[i - 1][j - coins[i - 1]] 表示第i个硬币只用一次，属于0-1背包。dp[i][j - coins[i - 1]] 表示第i个硬币重复使用，属于完全背包。
+5、初始化：首行首列
+  dp[i][0] = 1 表示使用前i个硬币，凑成总金额0的硬币组合数为1，即不用硬币就能凑成
+  dp[0][j] = 0 表示使用前0给硬币，凑成总金额j的硬币组合数为0，即没有硬币可以凑成。创建dp数组时已经有默认值
+6、遍历dp数组填表：第一层遍历硬币，第二层遍历金额，都从1开始，正序遍历。两个for循环先后都可以，因为计算当前状态只需要当前行左边的状态和上一行的状态
 7、返回结果：最后一个状态就是结果
+
+二维dp更新过程，从左到右，从上到下
+amount = 5, coins = [1, 2, 5]
+1  0  0  0  0  0
+1  1  1  1  1  1
+1  1  2  2  3  3
+1  1  2  2  3  4
+ */
+class Solution {
+    public int change(int amount, int[] coins) {
+        int n = coins.length;
+        int[][] dp = new int[n + 1][amount + 1];
+        for (int i = 0; i <= n; i++) {
+            dp[i][0] = 1;
+        }
+        for (int i = 1; i <= n; i++) {
+            for (int j = 1; j <= amount; j++) {
+                if (j - coins[i - 1] >= 0) {
+                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
+                } else {
+                    dp[i][j] = dp[i - 1][j];
+                }
+            }
+        }
+        return dp[n][amount];
+    }
+}
+
+
+/*
+动态规划：完全背包，一维数组
+1、定义dp数组：dp[i] 表示凑成总金额i的硬币组合数
+2、状态转移方程：dp[i] = dp[i] + dp[i-coin]，即所有dp[i-coin]相加
+3、初始化：dp[0] = 1，表示凑成总金额0的硬币组合数为1，即不用硬币，方便后面推导
+4、遍历dp数组填表：
+   1）遍历顺序：
+     ① 第一个for循环遍历硬币数组，第二个for循环遍历dp数组的未知位置，根据条件获取dp数组的已知位置，根据状态转移方程取已知结果汇总计算未知结果
+     ② 先物品再背包是计算组合，先背包再物品是计算排列，必须正序遍历背包才能重复使用物品
+   2）遍历理解
+     ① 一维数组是滚动数组，每一轮滚动遍历中，未遍历的表示上一轮的旧状态，正在遍历的表示正在计算的状态，遍历过的表示本轮的新状态
+     ② 本轮遍历中，金额不够时，只能选择不用硬币，旧状态就是“不用”，所以只遍历金额足够的情况即可(i = coin 开始)
+5、返回结果：最后一个状态就是结果
+
+一维dp更新过程，从左到右
+amount = 5, coins = [1, 2, 5]
+1  1  1  1  1  1
+      2  2  3  3
+               4
  */
 class Solution {
     public int change(int amount, int[] coins) {
