例题
例题：518. 零钱兑换 II
概述：
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
朴素的二维完全背包
想法：
完全背包问题：即为假设可选择的物品为无限个，在数学本质上是组合问题。
在本例中，需要求取满足sum=amount的不重复组合数量。
显然，最先容易想到的是二维背包方法，即为遍历coins数组，选择当前所有可能的硬币数量。
定义dp[coins.size()][amount]，得出状态转移方程。
在这种情况下，事件复杂度为O(coins.size()*amount^2)，空间复杂度为O(coins.size()*amount)。
注意到dp过程中的数据传递只在[i]和[i+1]之间发生，此处优化了空间复杂度，但时间复杂度仍然不变。
这里我们给出一个示例代码：
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1, 0);
dp[0] = 1;
for(int i=0;i<=coins.size();i++) {
if(i==coins.size()) {
return dp[amount];
}
vector<int> temp(amount+1, 0);
for(int j=0;j*coins[i]<=amount;j++) {
int sum = j*coins[i];
for(int k=amount;k-sum>=0;k--) {
temp[k] += dp[k-sum];
}
}
swap(dp, temp);
}
return 0;
}
};
降维
尝试运行以上代码，发现虽然能通过测试，但是耗时高到天际，显然不是一个好的解决方案。
这里进入今天的主题，二维dp降阶。事实上在上文代码中已经完成了空间层面的降阶，只需要考虑时间层面。
我们模拟其中一次转移的代码，进入循环for(int i=0;i<=coins.size();i++) {...}
假设此时amount = 4，coins[i] = 2
dp初始状态为：
此时刚进入循环，vector temp暂时为空（全0）：
第1轮，选择coin number = 0，sum=0，temp[k] += dp[k-0]; 即为将dp中内容拷贝到temp中
第2轮，选择coin number = 1，sum=1*2=2，temp[k] += dp[k-2];
第3轮，选择coin number = 2，sum=2*2=4，temp[k] += dp[k-4];
第4轮，coin number = 3，sum=3*2=6, 6>4，退出本轮循环
由以上图可以看出，循环中每一次相加就相当于对整体数组做了一次向上平移，offset=2。
这里我们想要在一个循环中完成上述的所有工作，可以观察到如下公式：
temp[0] = dp[0]
temp[2] = dp[2] + dp[0] = dp[2] + temp[0]
temp[4] = dp[4] + dp[2] + dp[0] = dp[4] + temp[2]
......
那么我们可以考虑下标从小到大的累加，这样，较大的下标相加的时候就自动处理了前面的部分，在算法上这是一种前缀和(prefix)思想。
这样，我们有如下代码：
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1, 0);
dp[0] = 1;
for(int i=0;i<coins.size();i++) {
for(int j=coins[i];j<=amount;j++) {
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
};
此时的时间复杂度为O(coins.size()*amount)，空间复杂度为O(amount)。