数据狗挂面

最近又被裁了，求一波人品。
先上来面试官聊了聊他们公司干嘛的，然后问了我干嘛的。中间还让我说了一下我最有挑战性的项目，和那个挑战是什么。
白人但有口音的小哥

题目是地理面经的题，coin change的变种。这是求一个min coin change的具体方案。可能现

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

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

为什么喜欢他们的公司。

补充内容 (2023-01-18 07:49 +8:00):
小哥高抬贵手，决定给我再店面一次，看能不能救。

lz是对的 不能用greedy

1.     static List<Integer>[] memo;
   
2.     public static List<Integer> minCoinChangeWay(int tar, int[] coins) {
   
3.         memo = new ArrayList[tar + 1];
   
4.         return dfs(tar, coins);
   
5.     }
   
6. 
   
7.     private static List<Integer> dfs(int tar, int[] coins) {
   
8.         List<Integer> res = new ArrayList();
   
9.         if (tar == 0) return res;
   
10.         if (memo[tar] != null) return memo[tar];
    
11.         int min = Integer.MAX_VALUE;
    
12.         for (int c : coins) {
    
13.             if (tar >= c) {
    
14.                 List<Integer> next = dfs(tar - c, coins);
    
15.                 if (next.size() < min) {
    
16.                     min = next.size();
    
17.                     res = new ArrayList(next);
    
18.                     res.add(c);
    
19.                 }
    
20.             }
    
21.         }
    
22.         return memo[tar] = res;
    
23.     }

复制代码

greedy优先把大数额的塞进去就好了 但是coin change还是推荐dp
对于coin change有些情况下greedy会失效（比如1 15 25， 目标30)，听说有一个多项式时间内检测能否用贪心的办法但是面试的时候那个检测几乎没用

之前常见的一个 coin[i] + coin[0] >= 2* coin[i-1] 条件也被1 15 25这个反例打破了

贪心有些testcase过不了，比如说【1， 2，5， 25】 33， 贪心的话 return 硬币数量是 0， 4， 0， 1
但答案实际上是1，1，1， 1

兄弟 先要和他们聊思路呀 要用greedy ，不要用bfs 或者dp

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

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

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

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

地理面经有 贪心是正解

coin change 的最小问题，贪心只对于某些input是可行的。
所以要看题目的coins 面值 是不是固定。如果是固定的且符合贪心解法，这种情况才可以用贪心。
这里有个证明
https://www.cnblogs.com/hapjin/p/5575112.html
https://www.cs.ucf.edu/~dmarino/ ... Greedy-Contests.pdf