LeetCode - Algorithms - 518. Coin Change 2

变个样，又不知道怎么解决了，动态规划确实不是那么好理解。根据上一题的经验，还是从递归入手，先实现递归，再琢磨动态规划的解决方案，就有点循序渐进的味道。正如 What is an easy way to understand the coin change problem in dynamic programming? 的一个回答所言：

Instead of thinking about filling a matrix, think in terms of the recurrence relation. I have seen a lot of people who try to think dynamic programming problems in terms of filling a table/array. But this approach is problematic. For example, if the state representation has more than two dimensions, then this approach does not help much.

The essence of dynamic programming is the idea of a state space and a recurrence relation between states. Once you figure that out for any problem, implementation is straightforward.

参考了这些，虽然还是没有完全理解，程序在leetcode上通过了，程序其实就短短的几行，The code has a O(NC) pseudo-polynomial complexity where N is the amount and C the number of input coins。

Java

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int change(int amount, int[] coins) {
    	int[] dp = new int[amount+1];
    	dp[0]=1;
    	for(int i=0;i<coins.length;i++) {
    		for(int j=coins[i];j<=amount;++j) {
    			dp[j]+=dp[j-coins[i]];
    		}    		
    	}
    	return dp[amount];        
    }
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 4 ms
  • Your runtime beats 78.72 % of java submissions.

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
	var dp = new Array(amount+1);
	for(var i=0;i<dp.length;i++)
		dp[i]=0;
	dp[0]=1;
	for(var i=0;i<amount;i++)
		for(var j=coins[i];j<=amount;++j)
			dp[j]+=dp[j-coins[i]];
	return dp[amount];    
};

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 60 ms
  • Your runtime beats 89.86 % of javascript submissions.