/** 完全背包
1. 状态定义：已经选择了硬币0...i且价值恰好为 j 的方案个数
2. 状态计算：以选 0到+INF 个第 i 个硬币的可能的和
3. 边界：f[0][0] = 1 不用硬币凑0元只有一种方案

线性DP; 阶段 -> 代价 -> 选择
1.阶段保证"无后效性" , 本题中硬币的选择是阶段, 因为选a硬币和b硬币相互独立
2.代价是方案数, 
3.选择-> 最终转移的过程


*/

class Solution {


    public int change(int amount, int[] coins) {

        int n = coins.length ;
        int[] f = new int[amount+1];

        f[0] = 1;
        for(int i = 0; i < n; i ++){
            for (int j = coins[i]; j <= amount; j ++){
                f[j] += f[j-coins[i]];
            }
        }

        return f[amount];
    }

    public int change2(int amount, int[] coins) {

        int n = coins.length ;

        int[][] f = new int[n+2][amount+2];
        // for (int i = 0 ; i <= n ; i++ )f[i][0] = 1;
        f[0][0] = 1;

        for(int i = 1; i <= n; i ++){
            for (int j = 0; j <= amount; j ++){
                for (int k = 0 ; k * coins[i-1] <=j ; k++ ){
                    f[i][j] += f[i-1][j-k*coins[i-1]];
                }
// f[i][j]      = f[i-1][j-0*c[i]] + f[i-1][j-1*c[i]] + ... + f[i-1][j-k*c[i]]
// f[i][j-c[i]] =                    f[i-1][j-1*c[i]] + ... + f[i-1][j-k*c[i]]
// f[i][j]      = f[i-1][j-0*c[i]] + f[i][j-c[i]]
// f[i][j]      = f[i-1][j]        + f[i][j-c[i]]   
// f[j]         = f[j]             + f[j-c[i]] （正序遍历）
            }
        }

        return f[n][amount];
    }
}