题目来源
给一个钱数以及一些硬币，硬币可以无限取，问有多少种组合方案。
一看就是一道DP题，但是太久没刷题，手生。导致不会做==。
dp[i][j]表示只用前i种硬币，凑够数目j的组合数目。
则有dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j-coins[i-1]] : 0)。
代码如下：
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n = coins.size();
vector<vector<int>> dp(n+1, vector<int>(amount+1, 0));
dp[0][0] = 1;
for (int i=1; i<=n; i++) {
dp[i][0] = 1;
for (int j=1; j<=amount; j++) {
dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j-coins[i-1]] : 0);
}
}
return dp[n][amount];
}
};
然后可以将其简化为一维的，因为dp[i][j]只依赖于dp[i-1][j]和dp[i][j-coins[i-1]]，代码如下：
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n = coins.size();
vector<int> dp(amount+1, 0);
dp[0] = 1;
for (int coin : coins) {
for (int i=coin; i<=amount; i++)
//这里的dp[i-coin]实际上就是dp[i][j-coins[i-1]]，原dp[i]就是dp[i-1][j]
dp[i] += dp[i-coin];
}
return dp[amount];
}
};
