LeetCode - Algorithms - 322. Coin Change

被这题卡住了，因为动态规划好像不好理解，看《算法图解》第九章，说动态规划都从一个网格开始，需要具备 Overlapping Sub-problems 与 Optimal Substructure。上网找线索与提示，最后发现先用递归方式实现，再看动态规划的方案就好理解些。主要参考了这几个：

原来 Change-making problem 是 Knapsack problem 的一类，背包问题还属于NP问题呢。

此题递归方式的实现是指数时间复杂度，跟动态规划的实现相比差距确实极其明显。递归方式的解法完全不可用，输入[1,2,5],100则报Time Limit Exceeded。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int coinChange(int[] coins, int amount) {
    	if (amount==0) return 0;

    	int n=-1;

    	int[] MC = new int[amount+1];
    	MC[0]=0;
    	for(int i=1;i<=amount;i++) {
    		MC[i] = Integer.MAX_VALUE;
    	}

    	for(int i=1;i<=amount;i++) {
    		for(int j=0;j<coins.length;j++) {
    			if (i>=coins[j]) {
    				int numCoins = MC[i-coins[j]];
    				if (numCoins!=Integer.MAX_VALUE && (numCoins+1<MC[i])) {
    					MC[i] = numCoins+1;
    				}
    			}
    		}
    	}
    	n=MC[amount];

    	if (n==Integer.MIN_VALUE || n==Integer.MAX_VALUE || n==0) n = -1;
    	return n;      
    }
}

Submission Detail

  • 182 / 182 test cases passed.
  • Runtime: 37 ms
  • Your runtime beats 28.19 % of java submissions.

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
	if (amount==0) return 0;

	var n=-1;
	var MC = new Array(amount+1);
	MC[0]=0;
	for(var i=1;i<=amount;i++)
		MC[i]=Number.MAX_VALUE;

	for(var i=1;i<=amount;i++) {
		for(var j=0;j<coins.length;j++) {
			if (i>=coins[j]) {
				var cc = MC[i-coins[j]];
				if (cc!=Number.MAX_VALUE && (cc+1<MC[i]))
					MC[i] = cc+1;
			}
		}
	}
	n = MC[amount];

	if (n==Number.MIN_VALUE || n==Number.MAX_VALUE || n==0) n = -1;

	return n;    
};

Submission Detail

  • 182 / 182 test cases passed.
  • Runtime: 80 ms
  • Your runtime beats 95.69 % of javascript submissions.