一道有趣的GG面试题

leetcode 322  coin change。面试的followup 是规定每个硬币的次数，不是无限。

xixiaoxi 发表于 2017-2-2 05:56
我觉得你的算法应该不太对，比如我有1，2，21，25美分的硬币，target number是63。正确答案应该是21+21+2 ...

你没看到lz写的大大的
“并且对于1...m中每一种面值，都可以用你选出的硬币拼出。”
？？？

304671127 发表于 2017-2-2 06:10
leetcode 322  coin change。面试的followup 是规定每个硬币的次数，不是无限。

followup的话是直接用一个array记录每个硬币的使用次数 然后一样的dp就行了吗

kunge12345 发表于 2017-2-2 07:01
你没看到lz写的大大的
“并且对于1...m中每一种面值，都可以用你选出的硬币拼出。”
？？？

啊对，哈哈，不好意思，刚才没有看到这句话

kunge12345 发表于 2017-1-28 21:47
李口德330 patching array一样的思路，greedy

补充内容 (2017-2-2 07:33):

这个题应该是要用dp，greedy会产生错误比如9，【5， 3， 1】用greedy就是1个5，4个1，但是用dp就可以知道是3个3

再看一遍题目，我请问你1你如何cover？嗯？

bigbearlake 发表于 2017-2-5 14:59
这个题应该是要用dp，greedy会产生错误比如9，【5， 3， 1】用greedy就是1个5，4个1，但是用dp就可以知道 ...

题目说要cover1到9，我请问你1你如何cover？

补充内容 (2017-2-5 22:54):
“比如9，【5， 3， 1】用greedy就是1个5，4个1，但是用dp就可以知道是3个3”

你这个情况用greedy应该是2个1，1个3，1个5

我的理解是m肯定能用它给的硬币拼出来，让我们找一个用硬币数最少的解法，如果要找出所有解法来估计要用dfs了
我用DP写了一下, prev里面保存了上次用的硬币

1. #include <vector>
   
2. #include <climits>
   
3. #include <unordered_map>
   
4. #include <iostream>
   
5. using namespace std;
   
6. 
   
7. unordered_map<int,int> coinChanging(vector<int> coins, int m) {
   
8.         vector<int> dp(m+1, 0), prev(m+1, 0);
   
9.         dp[0] = 0;
   
10.         for (int i = 1; i <= m; ++i) {
    
11.                 dp[i] = INT_MAX;
    
12.                 for (int j = 0; j < coins.size() && i >= coins[j]; ++j) {
    
13.                         if (dp[i-coins[j]]+1 < dp[i]) {
    
14.                                 dp[i] = dp[i-coins[j]]+1;
    
15.                                 prev[i] = coins[j];
    
16.                         }
    
17.                 }
    
18.         }
    
19.         cout << "min coins used: " << dp[m] << endl;
    
20.         unordered_map<int,int> res;
    
21.         int cur = m;
    
22.         while (cur != 0) {
    
23.                 ++res[prev[cur]];
    
24.                 cur -= prev[cur];
    
25.         }
    
26.         return res;
    
27. }
    
28. 
    
29. 
    
30. int main() {
    
31.         vector<int> coins = {1,2,21,25};
    
32.         for (auto& a: coinChanging(coins, 63)) {
    
33.                 cout << "coin " << a.first << ": " << a.second << endl;
    
34.         }
    
35.         for (auto& a: coinChanging({1,3,5}, 9)) {
    
36.                 cout << "coin " << a.first << ": " << a.second << endl;
    
37.         }
    
38.         for (auto& a: coinChanging({1,5}, 9)) {
    
39.                 cout << "coin " << a.first << ": " << a.second << endl;
    
40.         }
    
41.         for (auto& a: coinChanging({1,5}, 10)) {
    
42.                 cout << "coin " << a.first << ": " << a.second << endl;
    
43.         }
    
44.         return 0;
    
45. }

复制代码

至少有一枚硬币价值1，不然1本身无法表示。
有了这个，f(n)转化为价值为1的硬币和dp(n-1)。然后dp(n-1)用传统的dp。此时不再受1...m都可以表示的限制，因为有了1。

补充内容 (2017-2-11 02:15):
我想错了，请自动忽略我的回复。不好意思

其实dp(n-1)可以不用dp，贪心就可以？

补充内容 (2017-2-11 02:16):
我想错了，请自动忽略我的回复。不好意思