My code:
public class Solution {
private int min = -1;
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount < 0)
return -1;
else if (amount == 0)
return 0;
Arrays.sort(coins);
int ret = helper(coins, amount, coins.length - 1, 0);
return (ret == Integer.MAX_VALUE ? -1 : ret);
}
private int helper(int[] coins, int amount, int end, int counter) {
if (amount == 0)
return counter;
else if (amount < 0)
return Integer.MAX_VALUE;
else if (end < 0)
return Integer.MAX_VALUE;
int contain = helper(coins, amount - coins[end], end, counter + 1); // contain coins[end]
int miss = helper(coins, amount, end - 1, counter); // miss coins[end]
return Math.min(contain, miss);
}
}
這個解法是超時的趟薄。
采用了 backtracing 的思想堪夭，復(fù)雜度達(dá)到了驚人的 O(2 ^ n)
其實這道題目原型不就是 combination 嗎？
combination 要求你返回所有組合，而這個，是讓你返回所有組合中size最小的庐椒。
看了答案后，正確解法如下蚂踊，
My code:
public class Solution {
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount < 0)
return 0;
if (amount == 0)
return 0;
int[][] dp = new int[amount + 1][coins.length]; // for getting amount i, using coins[] from 0 to j, how many coins
for (int i = 0; i < dp[0].length; i++)
dp[0][i] = 0;
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
int contain = -1;
if (i - coins[j] >= 0)
contain = (dp[i - coins[j]][j] == -1 ? -1 : dp[i - coins[j]][j] + 1);
int miss = -1;
if (j >= 1)
miss = dp[i][j - 1];
if (contain == -1 && miss == -1)
dp[i][j] = -1;
else if (contain == -1 || miss == -1)
dp[i][j] = (contain == -1 ? miss : contain);
else
dp[i][j] = Math.min(contain, miss);
}
}
return dp[dp.length - 1][dp[0].length - 1];
}
}
采用backtracking 的方法约谈，為什么復(fù)雜度會那么高？
因為里面有大量的重復(fù)的case犁钟，一次次地被再次訪問棱诱。
而使用了 dp， 將已經(jīng)完成的結(jié)果全部存起來涝动，下次要用的時候迈勋，直接訪問，就可以了醋粟。不用再次推導(dǎo)靡菇。這也是dp的意義。
**
將已經(jīng)獲得的結(jié)果存起來米愿，下次使用就不需要再花時間求了厦凤。避免了重復(fù)時間。
**
參考網(wǎng)頁：
http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
另外吗货，這道題目要求的是最小coins組合泳唠，返回個數(shù)。
也可以求宙搬，達(dá)到target的所有組合個數(shù)笨腥。這樣, dp[i][j] 的含義，就是達(dá)到i勇垛，由coins[0] - [j]脖母，有多少種組合個數(shù)。 dp[0][j] = 1
也可以闲孤，再進(jìn)一步谆级，做成 combination.
Combination 復(fù)雜度是 O(2 ^ n)
而用這個dp，思路如下，
使用一個HashMap, key = i * row + j , which should be unique
value = its set for target.
那么肥照，dp[i][j]時脚仔，
首先，
如果 dp[ i - coins[j] ] [j] = 0, 那么 (i, j) -> empty set
如果 dp[ i - coins[j] ] [j] > 0, 那么dp[i][j] = dp[ i - coins[j] ] [j] + 1,
然后舆绎，取出( ( i - coins[j] ) , j) 對應(yīng)的set鲤脏，深拷貝一份，插入 coins[ i ],
將整體插入到 (i, j) -> set 的HashMap 中吕朵。
我覺得是可行的猎醇。但可能會出現(xiàn)重復(fù)問題。
dp是個很大的問題努溃，最近的理解在逐步加深硫嘶。
去除掉重復(fù)情況，類似于一個HashMap
另外梧税，HashSet沦疾， contains的復(fù)雜度，最壞情況可能是O(n)
HashSet 的底層是由 HashMap 實現(xiàn)的贡蓖。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) {
return -1;
}
if (amount == 0) {
return 0;
}
Arrays.sort(coins);
int[] dp = new int[amount + 1];
for (int i = 0; i < coins.length; i++) {
if (coins[i] <= amount) {
dp[coins[i]] = 1;
}
}
for (int i = 1; i <= amount; i++) {
if (dp[i] != 0) {
continue;
}
else {
int j = coins.length - 1;
int base = Integer.MAX_VALUE;
for (; j >= 0; j--) {
if (coins[j] > i) {
continue;
}
else if (dp[i - coins[j]] == 0) {
continue;
}
else {
base = Math.min(base, 1 + dp[i - coins[j]]);
}
}
dp[i] = (base == Integer.MAX_VALUE ? 0 : base);
}
}
return dp[amount] == 0 ? -1 : dp[amount];
}
}
不知道為什么之前會用 二維DP來做曹鸠？
這次做煌茬，直接就想到了一唯DP斥铺，并且寫了出來，雖然提交了好幾次坛善。
這道題目和 perfect squares 很相似晾蜘，都是用幾個給定的數(shù)，來湊這個數(shù)眠屎，求最小的次數(shù)剔交。
我的思路是，對于不能湊出來的改衩，就讓他的值保持0岖常，
比如，
我們要湊一個 i
我們有 coins[],
那么 就
拿coins里面的一個個面值來試葫督，
如果 dp[i - coins[i]] == 0, 那么就代表不能被湊出來竭鞍，那么就換下一個面值。
如果可以被湊出來橄镜，求出最小的那個值偎快。
dp[i] 表示的是， 湊錢到i需要的最少的個數(shù)洽胶。
O(amount * coins.length）
Anyway, Good luck, Richardo! -- 08/18/2016
