深入浅出零钱兑换问题——背包问题的套壳

前言

在本篇文章当中主要通过介绍两个算法题，从最基本的问题开始深入浅出零钱兑换问题，帮助大家从动态规划的本源深入理解问题当中的原理，并且学会自己分析问题，分析数据之间的依赖关系，通过分析这种关系自己推导算法的优化过程，再也不怕类似于背包问题的算法题了。

零钱兑换

题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例

示例1

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
1
2
3

示例2

输入：coins = [2], amount = 3
输出：-1
1
2

状态表示和状态转移方程

在求解动态规划问题的时候通常的步骤有以下几个：

• 寻找能够表示状态的数组dp，即我们需要寻找dp的含义，分析需要用几纬数组表示具体的状态。
• 通过分析问题，寻找动态转移公式。
• 初始化状态数组。
• 通过分析动态转移方程，确定数组的遍历顺序。

状态表示数组

在背包问题当中通常都是用一个二维数组表示数据的状态，在这个问题当中我们使用一个二维数组dp表示我们需要的状态：

dp[i][j]表示使用coins前i种面额的硬币表示金额等于j时使用的最少的金币，那么我们最终答案就是dp[N][amount]，他表示使用coins数组当中所有面额的硬币表示amount需要的最少的硬币个数。

寻找动态转移方程

在确定了状态表示的数组之后，现在我们就需要分析出动态转移方程了，在这个问题当中对于每一种面额的硬币我们都有两种选择：选和不选，但是在这个问题当中题目已经说明了对于每一种货币都可以认为是无限的，如果我们不选择，那这种情况比较简单，但是如果选择了这种情况就比较复杂了：

• 不选，这种情况比较简单，比如对于dp[i][j]，如果第i种面额的货币不选择，那么说明只使用前i - 1种面额的货币，那么dp[i][j] = dp[i - 1][j]，也就是说明如果使用前i种面额的货币去表示总额为j，但是不选择第i种面额的货币，就相当于使用前i-1种货币去表示j，那么需要的货币个数跟使用前i-1种货币去表示j需要的货币数目是相等的。
• 选，这种情况看起来就比较复杂了，因为我们需要确定是选一次，还是选两次，…，还是选N次，但是其实仔细思考一下我们可以使用一个类似递归的形式去解决这个问题，如果选择那么dp[i][j] = dp[i][j - coins[i]] + 1，我们仔细分析一下这个公式，相当于在总金额等于j的情况下先使用一次第i个面额的硬币，但是因为我们的硬币是无限的，现在我们还是可以选择第i个硬币，相当于总金额等于j - coins[i]而且可以使用前i个硬币的情况下，需要的最少的硬币个数，这就解决了是选一次还是选N次的问题了，而在上面的公式当中加一的原因是使用了一次第i种硬币。

很显然我们需要从上面两种情况当中选择需要的硬币最少的一种方法，因此综合上面的结果又如下的动态转移方程：
$$dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i]]+1)$$
其实上面这个问题的分析过程跟完全背包可以说是一模一样，如果你对完全背包感兴趣，你可以阅读这篇文章完全背包。

初始化状态数组

上面的问题分析过程当中，我们已经分析出来了动态转移方程，这个过程和完全背包非常相似，但是这个问题比完全背包还稍微复杂一点，因为不一定能够寻找到这样一种组合凑成的总金额等于题目当中规定的数目。我们用-1表示找不到这样一种组合能够表示。

• 在正式初始化之前先将dp数组第一行当中的数据全部初始化为-1。
• 初始化第一行代码如下：

for (int i = 0; i * coins[0] <= amount; i++) {
    dp[0][i * coins[0]] = i;
}
1
2
3

dp数组的第一行表示只使用第一种面额的硬币，因此只有第一种硬币面额的整数倍总金额才能使用第一种硬币进行表示，而且对应的硬币个数等于$\frac{amout}{coins[0]}$。

再看状态转移数组：

• 如果dp[i][j - coins[i]] == -1，那么就不能通过选择第i种硬币进行表示，在这种情况下，我们只能通过选择前i-1一种货币进行表示，即dp[i][j] = dp[i - 1][j]。可你你会有疑问，如果也不能使用前i-1种物品进行表示呢？没关系，如果不能表示那么dp[i - 1][j] == -1，那么赋值之后dp[i][j]也等于-1，也是不能表示的。
• 如果dp[i][j - coins[i]]不等于-1，但是dp[i - 1][j]等于-1，那么dp[i][j] = dp[i][j - coins[i]] + 1。
• 如果两者都不等于-1，那么我们就有如下的状态转移公式了：

$$dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i]]+1)$$

代码

class Solution {
  public int coinChange(int[] coins, int amount) {
    int[][] dp = new int[coins.length][amount + 1];
    Arrays.fill(dp[0], -1);
    for (int i = 0; i * coins[0] <= amount; i++) {
      dp[0][i * coins[0]] = i;
    }
    for (int i = 1; i < coins.length; i++) {
      for (int j = 0; j <= amount; j++) {
        // 如果要使用对应的硬币 
        // 总金额数目肯定要大于硬币的面额
        if (j >= coins[i]) {
          if (dp[i][j - coins[i]] == -1)
            dp[i][j] = dp[i - 1][j];
          else if (dp[i - 1][j] == -1)
            dp[i][j] = dp[i][j - coins[i]] + 1;
          else
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i]] + 1);
        } else {
          // 否则只能使用前 i-1 种硬币
          dp[i][j] = dp[i - 1][j];
        }
      }
    }
    return dp[coins.length - 1][amount];
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

上面的代码体现的就是完全背包 的思想，在题目当中硬币可以使用无限次，如果只能使用一次的话，问题就转换成01背包了，那么动态转移方程就为：
$$dp[i][j]=min(dp[i-1][j],dp[i-1][j-coins[i]]+1)$$

单行数组优化

根据动态转移方程$dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i]]+1)$，我们可以得到dp数组当中数据之间的依赖关系，他们的关系如上图所示，dp[i][j]依赖的数据为它上一行同列的位置，和第i行前面的某些数据，事实上我们可以使用单行数组去进行实现，我们使用的循环还是一样的，但是使用的数组有所变化，从之前的二维数组变成一维数组。当我们遍历到单行数组第j个数据的时候，第j个数据还是上一行的状态，但是单行数组的下标从0到j-1的位置数据的状态已经从上一行更新了，这些数据的状态相当于二维数组的dp[i]这一行的状态，而这正好可以满足动态转移方程的需求，因为在动态转移方程当中，dp[i-1][j]依赖的数据全部符合条件，单行数组当中的下标为j数据等于dp[i][j]，单行数组下标为x的数据等于dp[i][x]，其中$0\le x\le j$，这里你可以结合代码、文字和图片进行理解，理解效果会更加好一点。

class Solution {
  public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, -1);
    dp[0] = 0;
    for (int i = 0; i < coins.length; i++) {
      for (int j = coins[i]; j <= amount; j++)  {
        if (dp[j - coins[i]] != -1) {
          if (dp[j] == -1) {
            dp[j] = dp[j - coins[i]] + 1;
          }else
            dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
        }
      }
    }
    return dp[amount];
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

另一种角度思考问题

在上面的文章当中，我们是使用-1去表示不能够找到一个组合满足总金额数目。我们可以先将数组当中所有的数据全部初始化成amount + 1，这个是硬币的上界，如果我们全部使用一块的硬币进行兑换，结果是amount，因此最大的值不会超过amount + 1，因为在动态转移方程当中求的是最小值，因此在进行状态转移的时候不会选择这个值，因此下面的代码也是正确的！！！

class Solution {
  public int coinChange(int[] coins, int amount) {
    int max = amount + 1;
    int[] dp = new int[amount + 1];
    for (int j = 0; j < dp.length; j++) {
      dp[j] = max;
    }
    dp[0] = 0;
    for (int i = 0; i < coins.length; i++) {
      for (int j = coins[i]; j <= amount; j++) {
        if (dp[j - coins[i]] != max) {
          dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
        }
      }
    }
    return dp[amount] == max ? -1 : dp[amount];
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

零钱兑换 II

题目

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例

示例1

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
1
2
3
4
5
6
7

示例2

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
1
2
3

状态表示和状态转移方程

状态表示数组

在这个问题当中我们也是使用一个二维数组表示我们的状态dp[i][j]。这个表示使用前i个硬币，总金额为j的情况下，能够找到多少种组合方式，是硬币的和等于总金额数。

在这道题目当中我们也可以使用无数次硬币，因此这也是一个完全背包问题。

寻找动态转移方程

对于每一种硬币同样的有两种情况选择和不选择，每一种情况都有不同的组合，因此最终的组合数目就是将这两个结果相加：

• 选择，在这个情况下我们能够获得不同的组合数就是dp[i][j - coins[i]]，这个代码的含义就是选择一次第i个硬币，因为有无数个硬币，因此这个结果就等于使用前i个硬币组合总金额为j-coins[i]时，一共有多少个组合。
• 不选择，如果不进行选择，那么就相当于使用前i - 1个硬币，组合总金额为j时，一共有多少个组合。

因此最终的组合数的个数就是上面两种方式的不同组合个数相加，因此我们的动态转移方程为：
$$dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]];$$

初始化状态数组

在初始化dp数组的第一行的时候，只有是第一个硬币的整数倍的总金额才能进行匹配，如果不能匹配，那么不同的组合的数目就等于0，能够进行匹配的组合数也只有一个，那就是使用的硬币全是第一种硬币。在这里需要注意的是当总金额等于0的时候，也是有一种组合方式的，那就是没有一个硬币，这也是一种组合方式，就相当于集合的空基，因此初始化代码如下：

for (int i = 0; i * coins[0] <= amount; i++) {
  dp[0][i * coins[0]] = 1;

1
2
3

代码

class Solution {
  public int change(int amount, int[] coins) {
    int[][] dp = new int[coins.length][amount + 1];
    // dp[i][j] 的含义：前 i 个钱 容量 j 有多少种方法
    for (int i = 0; i * coins[0] <= amount; i++) {
      dp[0][i * coins[0]] = 1;
    }
    for (int i = 1; i < coins.length; i++) {
      for (int j = 0; j <= amount; j++) {
        if (j >= coins[i]) {
          dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
        } else
          dp[i][j] = dp[i - 1][j];
      }
    }
    return dp[coins.length - 1][amount];
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

其实这道题也有对应的01背包问题，在这道题目当中是完全背包问题的变种，如果所有的硬币只能够使用一次的话，那么动态转移方程如下：
$$dp[i][j]=dp[i-1][j]+dp[i-1][j-coins[i]];$$

单行数组优化

class Solution {
  public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    // dp[i][j] 的含义：前 i 个钱 容量 j 有多少种方法
    dp[0] = 1;
    for (int i = 0; i < coins.length; i++) {
      for (int j = coins[i]; j <= amount; j++)
        dp[j] += dp[j - coins[i]];
    }
    return dp[amount];
  }
}
1
2
3
4
5
6
7
8
9
10
11
12

这个优化的原理和第一题也是一样的，通过分析动态转移方程，看单行数组是否能够满足动态转移方程的要求，如果能够满足的话，那就能够进行单行数组优化，反之不能进行优化，而在这个问题当中，数据依赖关系和第一题是一样的，dp[i][j]依赖的数据是dp[i - 1][j]和dp数组第i行前j - 1个数据，根据第一题的分析，我们是可以使用单行数组进行优化的！！！

总结

在本篇文章当中主要给大家介绍了两道零钱兑换的问题，在本文当中的这两道题目都是属于完全背包的变种，如果要彻底弄懂这个问题的话就需要好好分析动态转移方程和数据之间的依赖关系，通过分析数据之间的依赖关系，我们自己也可以从零推导优化过程。在这两道问题当中硬币都可以使用无数次，如果将能够使用的硬币只能够使用一次的话，那么这个问题就变成01背包的变种问题了。

---

更多精彩内容合集可访问项目：https://github.com/Chang-LeHung/CSCore

关注公众号：一无是处的研究僧，了解更多计算机（Java、Python、计算机系统基础、算法与数据结构）知识。