Saved from https://leetcode.com/problems/coin-change/

lc322

class Solution {
    // The unbounded knapsack problem
    // dp[i][j]: the fewest # coins among 0 to i-1 to make up to amount j
    // dp[i][j] = min(dp[i-1][j], dp[i-1][j-coins[i]] + 1, dp[i][j-coins[i]] + 1)
    // since dp[i][j-coins[i]] includes dp[i-1][j-coins[i]], thus:
    // dp[i][j] = min(dp[i-1][j],  dp[i][j-coins[i]] + 1)
    // dp[i][j] < 0 means there is no solution.
    // 
    // Time: O(n * amount)
    // Space: O(n * amount)
    public int coinChange(int[] coins, int amount) {
        int[][] dp = new int[coins.length + 1][amount + 1];
        int MAX_VALUE = Integer.MAX_VALUE-1;
        Arrays.fill(dp[0], MAX_VALUE);
        dp[0][0] = 0;
        for (int i = 1; i < coins.length + 1; i++) {
            int currCoin = coins[i-1];
            for (int j = 0; j <= amount; j++) {
                int min = dp[i-1][j];
                if (j >= currCoin) {
                    min = Math.min(min, dp[i][j-currCoin] + 1);
                }
                dp[i][j] = min;
            }
        }
        return dp[coins.length][amount] == MAX_VALUE ? -1 : dp[coins.length][amount];
    }
}