Java easy understand code DP


  • 2
    K
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount < 0) {
            return -1;
        }
        int[] f = new int[amount + 1];
        f[0] = 0;
        for (int coin : coins) {
            if (coin > amount) {
                break;
            }
            f[coin] = 1;
        }
        for (int i = 1; i <= amount; i++) {
            if (f[i] == 0) {
                f[i] = Integer.MAX_VALUE;
            }
        }
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i && f[i - coins[j]] != Integer.MAX_VALUE) {
                    f[i] = Math.min(f[i], 1 + f[i - coins[j]]);
                }
            }
        }
        return f[amount] == Integer.MAX_VALUE ? -1 : f[amount];
    }

  • 0
    E

    Do we need "if (f[i] == 0)" in "for (int i = 1; i <= amount; i++)"?
    looks like the "f" array only has 0 in index 0 but "i" starts from 1.


  • 0
    N

    for (int coin : coins) {
    if (coin > amount) {
    break;
    }
    f[coin] = 1;
    }

    This part, so if we use int coin : coins, the coin will be in increasing order automatically? Otherwise, if the coins is [230, 250, 3] and amount is 233, then we break at coin = 250 and f[3] is never set to be 1.


  • 0

    hey, think of this, when you init an array, what is the initial value for all the array members?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.