// @Title: 零钱兑换 II (Coin Change II)
// @Author: qisiii
// @Date: 2024-09-26 19:49:39
// @Runtime: 8 ms
// @Memory: 47.9 MB
// @comment: 完全背包
// @flag: GREEN
class Solution {
    public int change(int amount, int[] coins) {
        // dp[i][j]代表的是0-i个金额任取刚好达到j的次数
        int[][] dp = new int[coins.length][amount + 1];
        //第一行只能可以模除成功，就代表一定能达到
        for(int j=0;j<=amount;j++){
            if(j%coins[0]==0){
                dp[0][j]=1;
            }
        }
        //不选也是一种方案，之所以初始化为1，是假如[1,2] 2的情况，只有11和2这两种方案，
        //11代表的是dp[i - 1][j]，2则是dp[i][j - coins[i]]
        for(int i=0;i<coins.length;i++){
            dp[i][0]=1;
        }
        for (int i = 1; i < coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                if (coins[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
                }
            }
        }
        return dp[coins.length-1][amount];
    }
}