【DP】完全背包问题｜Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

一、题目概述

LeetCode 518. 零钱兑换 II

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

示例 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


示例 2:

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


示例 3:

输入: amount = 10, coins = [10] 
输出: 1
复制代码

注意:

你可以假设：

0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数

题干分析

可以把这个问题转化成背包问题，描述如下：

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

动态规划标准套路：

1. 第一步要明确：状态 和 选择
2. 第二步要明确：dp 数组的定义
3. 第三步：根据 “选择”，思考状态转移的逻辑

1. 第一步要明确：状态 和 选择

1. 状态：“背包的容量” 和 “可选择的物品”
2. 选择：“装进背包” 或者 “不装进背包”

2. 第二步要明确：dp 数组的定义

1. dp数组的定义：dp[i][j] 表示若只使用前 i 个物品，当前背包的容量为 j 时，有 dp[i][j] 种方法可以装满背包。

   换句话：若只使用 coins 中的前 i 个硬币的面值，想凑出金额 j，有 dp[i][j] 种凑发。

2. 最终答案：dp[N][amount]，其中 N 为 coins 数组的大小。

3. base case：dp[..][0] = 1 和 dp[0][..] = 0

3. 第三步：根据 “选择”，思考状态转移的逻辑

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

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

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

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

二、思路实现

    public int numberOfCoinCombinationDP(int sum, int [] coins) {

        int [][] dp = new int[coins.length + 1][sum + 1];

        // base case
        for (int i = 0; i <= coins.length; ++i) dp[i][0] = 1;

        for (int i = 1; i <= coins.length; ++i) {
            for (int j = 1; j <= sum; ++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[coins.length][sum];
    }
复制代码

通过观察可以发现，dp 数组的转移只和 dp[i][...] 和 dp[i - 1][...] 有关，所以可以压缩状态，进一步降低算法的空间复杂度。

    public int numberOfCoinCombinationDPOsum(int sum, int [] coins) {

        int [] dp = new int[sum + 1];
        
        // base case
        dp[0] = 1;

        for (int i = 1; i <= coins.length; ++i) {
            for (int j = 1; j <= sum; ++j) {
                if (j - coins[i] >= 0) {
                    dp[j] = dp[j] + dp[j - coins[i]];
                }
            }
        }
        return dp[sum];
    }
复制代码