经典动态规划：完全背包问题

labuladong约 3662 字大约 12 分钟动态规划背包问题

Info

数据结构精品课open in new window 和递归算法专题课open in new window 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》open in new window 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
518. Coin Change IIopen in new window	518. 零钱兑换 IIopen in new window	🟠

零钱兑换 2 是另一种典型背包问题的变体，我们前文已经讲了经典动态规划：0-1 背包问题和背包问题变体：相等子集分割。

读本文之前，希望你已经看过前两篇文章，看过了动态规划和背包问题的套路，这篇继续按照背包问题的套路，列举一个背包问题的变形。

本文聊的是力扣第 518 题「零钱兑换 IIopen in new window」，我描述一下题目：

给定不同面额的硬币 coins 和一个总金额 amount，写一个函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

我们要完成的函数的签名如下：

int change(int amount, int[] coins);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

int change(int amount, vector<int>& coins);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def change(amount: int, coins: List[int]) -> int:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func change(amount int, coins []int) int

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var change = function(amount, coins) {

};

比如说输入 amount = 5, coins = [1,2,5]，算法应该返回 4，因为有如下 4 种方式可以凑出目标金额：

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

如果输入的 amount = 5, coins = [3]，算法应该返回 0，因为用面额为 3 的硬币无法凑出总金额 5。

Tip

至于零钱兑换 I，在我们前文动态规划套路详解写过。

我们可以把这个问题转化为背包问题的描述形式：

有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？

这个问题和我们前面讲过的两个背包问题，有一个最大的区别就是，每个物品的数量是无限的，这也就是传说中的「完全背包问题」，没啥高大上的，无非就是状态转移方程有一点变化而已。

下面就以背包问题的描述形式，继续按照流程来分析。

解题思路

第一步要明确两点，「状态」和「选择」。

状态有两个，就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」嘛，背包问题的套路都是这样。

明白了状态和选择，动态规划问题基本上就解决了，只要往这个框架套就完事儿了：

for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 计算(选择1，选择2...)

第二步要明确 dp 数组的定义。

首先看看刚才找到的「状态」，有两个，也就是说我们需要一个二维 dp 数组。

dp[i][j] 的定义如下：

若只使用前 i 个物品（可以重复使用），当背包容量为 j 时，有 dp[i][j] 种方法可以装满背包。

换句话说，翻译回我们题目的意思就是：

若只使用 coins 中的前 i 个（i 从 1 开始计数）硬币的面值，若想凑出金额 j，有 dp[i][j] 种凑法。

经过以上的定义，可以得到：

base case 为 dp[0][..] = 0, dp[..][0] = 1。i = 0 代表不使用任何硬币面值，这种情况下显然无法凑出任何金额；j = 0 代表需要凑出的目标金额为 0，那么什么都不做就是唯一的一种凑法。

我们最终想得到的答案就是 dp[N][amount]，其中 N 为 coins 数组的大小。

大致的伪码思路如下：

int dp[N+1][amount+1]
dp[0][..] = 0
dp[..][0] = 1

for i in [1..N]:
    for j in [1..amount]:
        把物品 i 装进背包,
        不把物品 i 装进背包
return dp[N][amount]

第三步，根据「选择」，思考状态转移的逻辑。

注意，我们这个问题的特殊点在于物品的数量是无限的，所以这里和之前写的 0-1 背包问题文章有所不同。

如果你不把这第 i 个物品装入背包，也就是说你不使用 coins[i-1] 这个面值的硬币，那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j]，继承之前的结果。

如果你把这第 i 个物品装入了背包，也就是说你使用 coins[i-1] 这个面值的硬币，那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]。

Note

由于定义中的 i 是从 1 开始计数的，所以 coins 的索引是 i-1 时表示第 i 个硬币的面值。

dp[i][j-coins[i-1]] 也不难理解，如果你决定使用这个面值的硬币，那么就应该关注如何凑出金额 j - coins[i-1]。

比如说，你想用面值为 2 的硬币凑出金额 5，那么如果你知道了凑出金额 3 的方法，再加上一枚面额为 2 的硬币，不就可以凑出 5 了嘛。

综上就是两种选择，而我们想求的 dp[i][j] 是「共有多少种凑法」，所以 dp[i][j] 的值应该是以上两种选择的结果之和：

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]];
return dp[N][W]

Note

有的读者在这里可能会有疑问，不是说可以重复使用硬币吗？那么如果我确定「使用第 i 个面值的硬币」，我怎么确定这个面值的硬币被使用了多少枚？简单的一个 dp[i][j-coins[i-1]] 可以包含重复使用第 i 个硬币的情况吗？

对于这个问题，建议你再仔回头细阅读一下我们对 dp 数组的定义，然后把这个定义代入 dp[i][j-coins[i-1]] 看看：

若只使用前 i 个物品（可以重复使用），当背包容量为 j-coins[i-1] 时，有 dp[i][j-coins[i-1]] 种方法可以装满背包。

看到了吗，dp[i][j-coins[i-1]] 也是允许你使用第 i 个硬币的，所以说已经包含了重复使用硬币的情况，你一百个放心。

最后一步，把伪码翻译成代码，处理一些边界情况。

我用 Java 写的代码，把上面的思路完全翻译了一遍，并且处理了一些边界问题：

int change(int amount, int[] coins) {
    int n = coins.length;
    int[][] dp = int[n + 1][amount + 1];
    // base case
    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];
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

int change(int amount, vector<int>& coins) {
    int n = coins.size();
    int dp[n + 1][amount + 1];
    // base case
    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];
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def change(amount: int, coins: List[int]) -> int:
    n = len(coins)
    dp = [[0] * (amount + 1) for _ in range(n + 1)]

    # base case
    for i in range(n + 1):
        dp[i][0] = 1

    for i in range(1, n + 1):
        for j in range(1, amount + 1):
            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]

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func change(amount int, coins []int) int {
    n := len(coins)
    dp := make([][]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, amount+1)
        dp[i][0] = 1
    }

    for i := 1; i <= n; i++ {
        for 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]
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var change = function(amount, coins) {
    var n = coins.length;
    var dp = new Array(n+1);
    for(var i=0; i<=n; i++){
        dp[i] = new Array(amount+1);
        dp[i][0] = 1; // base case
    }

    for (var i = 1; i <= n; i++) {
        for (var 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];
};

而且，我们通过观察可以发现，dp 数组的转移只和 dp[i][..] 和 dp[i-1][..] 有关，所以可以使用前文讲的动态规划空间压缩技巧，进一步降低算法的空间复杂度：

int change(int amount, int[] coins) {
    int n = coins.length;
    int[] dp = new int[amount + 1];
    dp[0] = 1; // base case
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= amount; j++)
            if (j - coins[i] >= 0)
                dp[j] = dp[j] + dp[j-coins[i]];
    
    return dp[amount];
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

int change(int amount, vector<int>& coins) {
    int n = coins.size();
    vector<int> dp(amount + 1);
    dp[0] = 1; // base case
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= amount; j++)
            if (j - coins[i] >= 0)
                dp[j] = dp[j] + dp[j-coins[i]];
    
    return dp[amount];
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def change(amount: int, coins: List[int]) -> int:
    n = len(coins)
    dp = [0] * (amount + 1)
    dp[0] = 1 # base case
    for i in range(n):
        for j in range(1, amount + 1):
            if j - coins[i] >= 0:
                dp[j] = dp[j] + dp[j - coins[i]]
                
    return dp[amount]

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func change(amount int, coins []int) int {
    n := len(coins)
    dp := make([]int, amount+1)
    dp[0] = 1 // base case
    for i := 0; i < n; i++ {
        for j := 1; j <= amount; j++ {
            if j-coins[i] >= 0 {
                dp[j] = dp[j] + dp[j-coins[i]]
            }
        }
    }
    return dp[amount]
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var change = function(amount, coins) {
    var n = coins.length;
    var dp = new Array(amount + 1).fill(0);
    dp[0] = 1; // base case
    for (var i = 0; i < n; i++) {
        for (var j = 1; j <= amount; j++) {
            if (j - coins[i] >= 0) {
                dp[j] = dp[j] + dp[j-coins[i]];
            }
        }
    }
    return dp[amount];
};

这个解法和之前的思路完全相同，将二维 dp 数组压缩为一维，时间复杂度 O(N*amount)，空间复杂度 O(amount)。

至此，这道零钱兑换问题也通过背包问题的框架解决了。

接下来可阅读：

背包问题变体之子集分割

引用本文的文章

目标和：背包问题的变体经典动态规划：0-1 背包问题

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释

# 解题思路

解题思路