背包问题是动态规划中的经典题型之一,需要反复咀嚼,感受它的魅力。本文以LeetCode 512 零钱兑换II为例进行讲解:
思路
- 对于动态规划类题目首先要分析题目中有哪几种状态和选择。以零钱兑换II为例,状态有两种:硬币面值种类和金额大小。选择也有两种:当前的硬币是否“放入”金额这个容器内(放或者不放)。
- 然后确定数组的含义,这一步至关重要,不同的含义会导致后面的操作完全不一样。本题是计算用所给不同面值的硬币凑成当前金额的方式有多少种,所以数组定义为在使用前种面值的硬币时,总共有多少种方式可以凑出当前金额。
每当“物品”要放入到“金额”这个口袋中时,有两种情况:
- 当口袋的剩余容量不小于物品的重量(硬币的价值),有两种操作方式:选择放入或者选择不放入。
- 当口袋的剩余容量小于物品的重量(隐蔽的价值),此时只能选择不放入。
根据以上两种情况,可以写出相关的伪代码:
if (j > coins[i])
选择将当前面值的硬币放入金额口袋
或者
选择不将当前面值的硬币放入金额口袋
else
只有一种选择,不将当前面值的硬币放入金额口袋
- 思考状态转移
- 将第种硬币放入剩余容量为的口袋内时,此时的结果取决于第种硬币放入剩余容量为的口袋内的组合数,即
- 不将第种硬币放入剩余容量为的口袋内时,此时的结果取决于上一种硬币放入剩余容量为的口袋内的组合数,即
- 当前口袋容量不小于当前硬币面值时,有两种可能的操作,所以此时的
- 当前口袋容量小于当前硬币面值时,只能有一种“不放回”操作,所以此时的
- 边界条件
一般情况下,状态有几种就需要考虑几种边界条件。当硬币面值的种类数为0时,对于任意非0金额口袋肯定是装不满的。当金额口袋容量为0时,我们不需要任何操作就相当于装满了这个口袋。
##边界条件
for (int i=0; i<=n; i++)
dp[i][0] = 1;
for (int i =0; i<=amount; i++)
dp[0][i] = 0;
- 编写代码
int change(int amount, vector<int>& coins) {
int n = coins.size();
if (amount == 0 && n == 0) return 1;
vector<vector<int>>dp(n+1, vector<int>(amount+1));
for (int i=0; i<n+1; i++)
dp[i][0] = 1;
//vector自动初始化为0,所以这里不再需要重复赋值来晚上边界条件
// for (int i=0; i<=amount; i++)
// dp[0][i] = 0;
for (int i=1; i<n+1; 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];
}