Google 二面 求乐高块数 用动态规划 不会做 求问

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

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

crazycodyman 发表于 2019-6-26 14:29
完全背包取件是无限的，这题的有限的取件，不一样吧？

那这算是多重背包？

实在不会就写dfs+memo吧 背包问题就是要背通式 唯有dfs memo是不需要背万能的

        很有用的信息！

leecx22 发表于 2019-6-27 02:21
那这算是多重背包？

是啊，这题如果是完全背包，那楼主的解法就没问题

1. public int minLego(int[][] legos, int target) {
   
2.         int m = legos.length;
   
3.         int[][] dp = new int[m+1][target+1];
   
4.         for(int i = 1; i <= target; i++) {
   
5.                 dp[0][i] = -1;
   
6.         }
   
7.         for(int i = 1; i <= m; i++) {
   
8.                 int lego = legos[i-1][0], num = legos[i-1][1];
   
9.                 for(int j = 1; j <= target; j++) {
   
10.                         dp[i][j] = -1;
    
11.                         for(int k = 0; k <= num; k++) {
    
12.                                 if(j < k * lego)
    
13.                                         break;
    
14.                                 if(dp[i-1][j - k * lego] != -1) {
    
15.                                         if(dp[i][j] == -1)
    
16.                                                 dp[i][j] = k + dp[i-1][j - k * lego];
    
17.                                         else
    
18.                                                 dp[i][j] = Math.min(dp[i][j], k + dp[i-1][j - k * lego]);
    
19.                                 }
    
20.                         }
    
21.                 }
    
22.         }
    
23.         return dp[m][target];
    
24. }

复制代码

写了一下代码，有错误的话请大神指出。

https://stackoverflow.com/questi ... ted-amount-of-coins

1. def solve(legos,target):
   
2.     dp = [[9999 for x in range(target+1)] for x in range(len(legos))]
   
3.     for i in range(len(legos)):
   
4.         for t in range(target+1):
   
5.             if t==0:
   
6.                 dp[i][t] = 0
   
7.             elif legos[i] == t:
   
8.                 dp[i][t] = 1
   
9.             elif legos[i]>t:
   
10.                 dp[i][t] = dp[i-1][t]
    
11.             else:
    
12.                 dp[i][t] = min(1 + dp[i-1][t-legos[i]],  dp[i-1][t])
    
13.     return dp[len(legos)-1][target]
    
14. 
    
15. legos = [1]*10+[2]*5+[3]*4+[5]

复制代码

写了一下python的，欢迎指正……bottom up的方法，9999代表无解

这是有限取件

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

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