一道 coin change 变种，求各路大神给点思路

给一个 tagert value 和 list of coins， 求最少的硬币，能组成[1 ～ target value]中所有的数比如： target value = 20， list= [1,2,5,10]
返回： 5 （1，2，2，5，10 能组成所有1～20的数）
如果没有则返回：-1

前几天做oa的时候遇到的，很多test case没过。请教各位大神有没有什么好的思路。





补充内容 (2019-4-7 07:27):
和原版coin change不一样的地方在于，原版只需要组成target value的最少硬币，这个问题需要组成【1～target value】中所有值的最少硬币

Greedy + DP，思路是，从1开始，每次加一个最大的可以加的硬币，加了以后，更新dp数组。其实这个题是必定有解的，因为如果没有一个面值为1的硬币的话，这题没有意义，有了面值为1的硬币的话，任何值都可以用很多1拼凑出来。不知lz是否记得一些测试样例，来证明这个代码不能解决的。

1. class Solution:
   
2. 
   
3.     def min_set_coins(self, coins, higest_amount):
   
4. 
   
5.         coins.sort()
   
6.         dp = [True] + [False for _ in range(higest_amount)]
   
7.         bag = []
   
8. 
   
9.         for amount in range(higest_amount+1):
   
10. 
    
11.             if dp[amount]:
    
12.                 continue
    
13.             
    
14.             for coin in reversed(coins):
    
15.                 if amount - coin < 0:
    
16.                     continue
    
17.                
    
18.                 bag.append(coin)
    
19. 
    
20.                 for i in range(amount):
    
21.                     if i + coin > higest_amount:
    
22.                         continue
    
23.                     dp[i+coin] = True
    
24.                 break
    
25. 
    
26.             if not dp[amount]:
    
27.                 return -1

复制代码

补充内容 (2019-4-6 16:45):
拷贝时，漏了最后一行：

return len(bag)

按我的理解，这道题可以用贪心法做。基本思路是，如果目前已经取了[C1, C2, ... Ct]这些硬币（升序排列且可能有重复值），且这些硬币能且只能够覆盖的最大范围是[1, K]（即无法覆盖任何大于K的数，且K==C1+C2+...+Ct），那么我下次取的C(t+1)应当是"<=K+1的最大硬币面值"，然后令K = K + C(t+1)。重复这个过程直到K >= target即可。

------- 以下说明正确性 ---------

这样得到的解集一定能够覆盖[1, target]。关键思路是：因为C(t+1)和[C1...Ct]范围内的某些或所有硬币组合能覆盖的范围能且只能是[C(t+1), K+C(t+1)]，那么"Ct+1<=K+1这个条件"保证了原来的覆盖范围[1, K]和这个新范围[C(t+1), K+C(t+1)]有交叉，因此这两者能合成一个新的连续覆盖范围[1, K+C(t+1)]。这样每一步都没有间断地扩展覆盖范围，所以最后返回时的解集一定能够不间断地覆盖[1, target]。

这样得到的解集一定最短：设对于某target value T，贪心法找到的解是：
[C1,  C2,  .. Ci .. , Ct-m, Ct-m+1, ..., Ct] （注意这个解集能覆盖的最大值K有可能>T）

假设存在一个更短的最优解（升序排列）
[C'1, C'2, .. C'i .. , C't-m]

那么首先一定有C'i<=Ci（如果不是这样，我们可考虑i最小的那对C'i > Ci(也就是说C'j <= Cj for all j in [0 i-1]。因为贪心法取的Ci是满足新范围中不出现间断的最大面值，所以如果在C'中取了比Ci还大的C'i以后，一定会出现覆盖范围间断的情况，而i以后的C'比C'i还大，更加无法弥补这个间断空隙，也就是说C'在i和之后的所有硬币取得没有任何意义。这和之前假设C'是最优解矛盾）

所以C'能覆盖的最大范围K' <= sum(C'1 ... C't-m) <=  sum(C1...Ct-m) = C中前t-m个硬币能覆盖的范围K(t-m)

又因为C'是最优解，所以有T <= K'；

由上两条件可知T <= K(t-m)。这说明如果C'是一个解，那么C的前t-m项也应该是一个解，那么贪心算法应该在取到C(t-m)就停下来，但是却没有停，那唯一的可能就是假设错误，也就是说不存在比贪心法结果更短的解。

-------------

这个说明比较粗糙，里面可能有些没说太清楚的地方，欢迎讨论。

这题简单，用动态编程就可以解决。

1. 
   
2. 
   
3. public int leastCoins(int[] coins, int amoun){
   
4. int[] dp = new int[amount + 1];
   
5. Arrays.fill(dp, -1);
   
6. dp[0] = 0;
   
7. for(int i=1; i<=amount; i++){
   
8.   int min = Integer.MAX_VALUE;
   
9.   for(int coin : coins){
   
10.      if(i-coin >=0 && dp[i-coin] != -1){
    
11.          min = Math.min(min, dp[i-coin] +1);
    
12.      }
    
13.   }
    
14.   if(min != Integer.MAX_VALUE) dp[i] = min;
    
15. }
    
16. 
    
17. return dp[amount];
    
18. }
    

复制代码

楼上的都好复杂啊，用bfs不行吗？（小白脸）

孙行者 发表于 2019-4-6 12:41
这题简单，用动态编程就可以解决。

感谢分享思路，这个是原版coin change 的解法，如果带入题目的例子，会返回组成 target value 的最少coin。
和题目问的有点不一样。题目需要能组成【1～target value】所有值的最少coin

目前唯一思路是暴力解，记录所有value的硬币组成方式，取并集。
有没有大神提供更优的想法？

stellari 发表于 2019-4-7 05:10
按我的理解，这道题可以用贪心法做。基本思路是，如果目前已经取了[C1, C2, ... Ct]这些硬币（升序排列且可 ...

看了好半天终于看懂了，这个贪心解法6爆了，感谢大神分享思路。

tinlittle 发表于 2019-4-7 07:43
Greedy + DP，思路是，从1开始，每次加一个最大的可以加的硬币，加了以后，更新dp数组。其实这个题是必定有 ...

感谢分享！6666，代码看了一遍，你和前面那位大神思路一样。
greedy是个好东西啊

这题有更简单的解法：

1. public int getMinCoins(int[] coins, int target){
   
2. 
   
3.         List<Integer> res = new ArrayList<>();
   
4.         Arrays.sort(coins);
   
5. 
   
6.         int amount = 1;
   
7.         while(amount <= target){
   
8.             
   
9.             boolean found = false;
   
10.             for(int i=coins.length-1; i>=0; i--){
    
11.                 if(amount - coins[i] >= 0){
    
12.                     res.add(coins[i]);
    
13.                     amount += coins[i];
    
14. 
    
15.                     found = true;
    
16.                     break;
    
17.                 }
    
18.             }
    
19.             
    
20.             if(!found) return -1;
    
21.         }
    
22. 
    
23.         return res.size();
    
24.     }

复制代码

补充内容 (2019-4-7 09:04):
这题因为前一个区域都被满满的覆盖了，加一个硬币，则新的范围也是全部覆盖的。这个解的时间复杂度应当是O(n). 感觉数学方法也能做，因为只要amount大于最大硬币，就用最大硬币延伸覆盖区域，结果时间复杂度是O(1).