JAVA 7 lines with DP, O(N) Space Complexity


  • 0
    Z

    public class Solution {
    public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];//initialize 0
    dp[0] = 1;
    for(int i = 0;i < coins.length;++i)
    for(int j = amount;j >= 1;--j)
    for(int k = j - coins[i];k >= 0;k -= coins[i])
    dp[j] += dp[k];
    return dp[amount];
    }
    }


Log in to reply
 

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