My Java DP Iterable solution 33 ms


  • 0
    M
    public int coinChange(int[] coins, int amount) {
        if (coins.length <= 0 || amount == 0) {
            return amount == 0 ? 0 : -1;
        }
        Arrays.sort(coins);
        int[] min = new int[amount + 1];
        for (int i = coins[0]; i <= amount; i++) {
    
            for (int coin : coins) {
                if (coin <= i) {
                    int prevIdx = i - coin;
                    int prevSolution = min[prevIdx];
                    if (prevIdx == 0 || (prevSolution != 0 && (min[i] == 0 || prevSolution + 1 < min[i]))) {
                        min[i] = prevSolution + 1;
                    }
                }
            }
        }
        return min[amount] != 0 ? min[amount] : -1;
    }

  • 0
    S

    nice, my DP solution takes 68ms :(


Log in to reply
 

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