Bottom Up

经典题目

322. Coin Change

// Basic idea: create an integer array with the length of amount + 1. 
// Use DP to construct the array from beginning.
// Whenever we reach a new index i, we check all the coin options
// and see whether we have calculated dp[i - coin] before.

// Time: O(n * S), n = size of the array, S = amount
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (i - coin >= 0 && dp[i - coin] != Integer.MAX_VALUE) {
                min = Math.min(min, dp[i - coin] + 1);
            }
        }
        dp[i] = min;
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}