4.26Amazon视频面试：coin change的变种

mc2 发表于 2019-5-23 07:48
我来说两种方法：

1. coins全部加上id, coin是这个coin的面值。DP[j] 是如果用这个coin能达到j钱数的最 ...

非常感谢仁兄的分享！

1. 0 那里我猜想如果换成 sys.maximum 会更加 make sense, 当然，不换也是非常好的思路了，谢谢！
2. 可否请教仁兄一下这个解法，我不是特别能够理解这个流程，或者发一个链接，有相关的 Dijkstra 这部分的讲解。

非常感谢！

请叫我热情老八 发表于 2019-5-22 13:18
非常感谢仁兄的分享！

1. 0 那里我猜想如果换成 sys.maximum 会更加 make sense, 当然，不换也是非常 ...

Dijkstra其实比较简单。老兄去tube查查很多讲解。在这个题目的关键就是用PriorityQueue，哪个amount更大就先处理哪个。虽然排序耗费时间但是确是一个时间和空间总体的良好折中方案。当然用Queue BFS也可以，不过空间耗费可能会大一些。

这题要动态解法真不好做，还会套到陷阱里面。迭代+greedy做法相当简单。

您好！
本帖隐藏的内容需要积分高于 160 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 160 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2019-5-23 11:22):
要修正一下，在返回值的时候要把long 转成int.
个人认为在面试的时候，先把题用自己能解的方法做出来。这样可以保底。

补充内容 (2019-5-23 13:14):
硬币应当排序，然后从最大硬币迭代。

chenyijia055 发表于 2019-5-4 16:13
想请教一下 greedy 怎么加？ 如过是单纯的从大的开始往后找，找到后就停止，那结果可能会不对。 比如这个 ...

我发了答案在后面。里面有详细说明。

孙行者 发表于 2019-5-23 11:46
我发了答案在后面。里面有详细说明。

谢谢了，code很不错， 但是感觉你这个不算是greedy，只是在recursion的时候做了一些优化 可以提早terminate  if(coinIdx < 0 || change > minChange) return。 如果是greedy的话应该像是按照某一个方法找 找到的第一个就是最优的结果。虽然你是从大往小找，但是这种找法好像也不能保证什么，一样需要继续去尝试小的值，然后比较。

孙行者 发表于 2019-5-23 11:17
这题要动态解法真不好做，还会套到陷阱里面。迭代+greedy做法相当简单。
**** 本内容被作者隐藏 ****

23楼的思路基本正确，但只是backtrace的思路。需要bacaktrace + greedy，大概就是backtrace从能用的最大面值coin开始，找到的第一个解就是最优解，直接break and return 就好。

调试了一下，修改了bug.

您好！
本帖隐藏的内容需要积分高于 160 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 160 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

leecode 322 可以看成这个followups 的特殊情况，没种硬币的数量也可以看成是有限的，最多 amount / coins[i] 个。这样的话都可以用同一种解法。都是背包问题。先是memo + dfs, 然后转化成dp. 可能是我太笨，我背包问题都不太会，只能多练。下面几道是leetcode 中关于背包的问题。https://leetcode.com/problems/coin-change/  https://leetcode.com/problems/partition-equal-subset-sum/  https://leetcode.com/problems/target-sum/  https://leetcode.com/problems/ones-and-zeroes/description/  https://leetcode.com/problems/last-stone-weight-ii/

MEMO + DFS

1. class Solution {
   
2.     public int coinChange(int[] coins, int amount) {
   
3.         return coinChange(coins, amount, new int[amount][coins.length], 0);
   
4.     }
   
5.    
   
6.     public int coinChange(int[] coins, int amount, int[][] memo, int index) {
   
7.         if (amount == 0) {
   
8.             return 0;
   
9.         }
   
10.         if (amount < 0 || index == coins.length) {
    
11.             return -1;
    
12.         }
    
13.         if (memo[amount - 1][index] != 0) {
    
14.             return memo[amount - 1][index];
    
15.         }
    
16.         
    
17.         int maxCoints = amount / coins[index];
    
18.         int min = Integer.MAX_VALUE;
    
19.         for (int i = 0; i <= maxCoints; i++) {
    
20.             int res = coinChange(coins, amount - i * coins[index], memo, index + 1);
    
21.             if (res != -1) {
    
22.                 min = Math.min(min, res + i);
    
23.             }
    
24.         }
    
25.         memo[amount - 1][index] = min == Integer.MAX_VALUE ? -1 : min;
    
26.         return memo[amount - 1][index];
    
27.     }
    
28. }

复制代码

背包DP 解法

1. class Solution {
   
2.     public int coinChange(int[] coins, int amount) {
   
3.         int[] dp = new int[amount + 1];
   
4.         int n = coins.length;
   
5.         dp[0] = 0;
   
6.         for (int i = 1; i <= amount; i++) {
   
7.             dp[i] = Integer.MAX_VALUE;
   
8.         }
   
9.         for (int i = 1; i <=n; i++) {
   
10.             for (int j = 0; j <= amount; j++) {
    
11.                 for (int k = 1; k <= j / coins[i - 1]; k++) {
    
12.                     if (dp[j - k * coins[i - 1]] != Integer.MAX_VALUE) {
    
13.                         dp[j] = Math.min(dp[j], dp[j - k * coins[i - 1]] + k);
    
14.                     }
    
15.                 }
    
16.             }
    
17.         }
    
18.         return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    
19.     }
    
20. }

复制代码