Coin Change

• 暴力递归解法 （DFS）
  • 对coins中的每一个可能的数都求Xi，这里可以知道Xi <= amount/c[i], 然后对其进行0~Xi的循环，recursive求解

• DP top down

  • dp(amount) = min dp(amount-c[i]) + 1,这里0<=i<=n-1
  • 发现有大量的重复计算，用一个表（数组保存已经计算了的值）

• DP bottom up

  • 注意dp不一定是从array来构建的，也可能从target来构建
  • dp(i) =min dp(i-c[j])+1, 0<=j<=n-1
  • 不能用Integer.MAX_VALUE，when it could +1，会溢出
    • 此时只需要用一个肯定确定的值即可，例如amount+1

class Solution {
    public int coinChange(int[] coins, int amount) {
        int len = coins.length;
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < len; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);    
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}