class Solution {
public int change(int amount, int[] coins) {
int[][] dp = new int [coins.length+1][amount+1];
//base
for(int i = 0;i<=coins.length;i++){
dp[i][0] = 1;
}
for(int i = 1;i<=amount;i++){
dp[0][i] = 0;
}
//转移状态
for(int i = 1;i <= coins.length;i++){
for(int j = 1;j <= amount;j++){
if(j < coins[i-1] ){//加不进去
dp[i][j] = dp[i-1][j];
}
else{//能加进去,但是可以加也可以不加
dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j];
}
}
}
return dp[coins.length][amount];
}
}
