题目
image.png
题解
题解1
特别要注意公式推导
// 状态 总金额，硬币个数
// 选择
// dp[i][j] 前i个硬币，组合为j金额的组合数
// 公式 dp[i][j]=dp[i-1][j] / 不选i + dp[i-1][j-coins[i]] / 选i ???
// 特别注意 dp[i][j-coins[i]]
class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[][] dp = new int[n + 1][amount + 1];
// base case
// dp[...][0] = 1
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++) {
// dp[i][j] = dp[i-1][j] + dp[i-1][j-coins[i-1]];
// j-coins[i-1] 的正负问题
if (j < coins[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
// dp[i][j] = dp[i-1][j] + dp[i-1][j-coins[i-1]]; // 错了
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
}
}
}
return dp[n][amount];
}
}
