/**
1. 完全背包问题,
2. 状态定义: f[i] 为凑i元需要的最小硬币数
    2.1 x < y 时, 凑y元可以依赖凑元, 反之不可以, 所以符合"无后效性"
    2.2 符合最优子结构
3. 状态计算: f[j] = MIN(f[j], f[j-coins[i]] + f[coins[i]])
4. 边界: f[~]  = INF, f[0] = 0, f[c[a]] = 1
*/

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0) return -1;
        int[] f = new int[amount + 1];
        Arrays.fill(f, Integer.MAX_VALUE >> 1);
        f[0] = 0;
        for (int i = 0; i < coins.length ; i ++) 
            if (coins[i] <= amount) f[coins[i]] = 1;

        for (int i = 1; i <= amount ; i ++)
            for (int j = 0 ; j < coins.length; j++)
                if (i >= coins[j]) f[i] = Math.min(f[coins[j]] + f[i - coins[j]], f[i]);

        return f[amount] == Integer.MAX_VALUE >> 1 ? -1 : f[amount];
    }
}