Easy understand Java solution with comments, Time: O(n*amount), Space: O(N)


  • 1
    W
    // 动态规划公式:dp[i] = Math.min(dp[i], 1+dp[i-coin])
    public static int coinChange(int[] coins, int N) {
    	int[] dp = new int[N + 1];
    	Arrays.fill(dp, Integer.MAX_VALUE);// 初始化用Integer.MAX_VALUE填充数组,表示无解
    	dp[0] = 0; // 不要忘了dp[0]=0!!
    	for (int i = 1; i <= N; i++) { // 从1到N动态规划
    		for (int coin : coins) { // 每次遍历所有coin
    			if (i >= coin && dp[i - coin] != Integer.MAX_VALUE) { // i>=coin且dp[i - coin]有解!
    				dp[i] = Math.min(dp[i], 1 + dp[i - coin]); // 递推公式
    			}
    		}
    	}
    	return dp[N] != Integer.MAX_VALUE ? dp[N] : -1; // 若dp[N]无解时返回-1
    }

Log in to reply
 

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