Java DP solution 27 ms


  • 9
    X
    int min = Integer.MAX_VALUE;
    int total = 1;
    int[] dp = new int[amount + 1];
    dp[0] = 0;
    while (total <= amount) {
        min = Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
    	int diff = total - coins[i];
    	if (diff > 0 && dp[diff] > 0 || diff == 0) {
    	    min = Math.min(min, dp[diff] + 1);
    	}
        }
        dp[total++] = (min == Integer.MAX_VALUE ? -1 : min);
    }
    return dp[amount];

  • 0
    M

    You can replace dp[total - coins[i]] with dp[diff]


  • 0
    X

    Good point. Have updated.


  • 0
    A

    i tried running this code and I got run time exception. Any thoughts?


Log in to reply
 

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