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

题目背景：有很多乐高，比如大小为1,2， 3， 5的乐高，给一个target，比如10，求问最少的乐高块数拼凑得到target，比如用两个大小为5的乐高可以得到target 10，也可以用10个大小为1的乐高得到target

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

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

片，如果只剩0片了，就不能再取了

求问大神，在每种乐高数量已知并且有限的情况下，怎么用动态规划做这题。。。。。。。  

这不就是经典的背包问题吗
设dp[i, j] = 前i个乐高拼出j的最小块数， 那么就是求dp[N, target]
dp[i, j] = dp[i-1, j-k*l[i]]+k, 0<=k<=j/l[i], where l[i] 是第i个乐高的大小

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. }

复制代码

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

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

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

硬币问题。。经典题。。。送分题。。。。

yeah......和楼上2位反应一致。。这是经典硬币题，LZ再刷题时，一定要按类别刷。这题应该是DP类里的基础题。
Capital One 的new grad 面试一天到晚考这题。

这就是个“完全背包”。可参见《背包问题九讲》。

谢谢楼上各位指道儿。。。  自己太弱了。。。。

看完才發現我也是太弱的那個

这不是完全背包吗

leecx22 发表于 2019-6-26 09:36
这不是完全背包吗

完全背包取件是无限的，这题的有限的取件，不一样吧？

Sengo 发表于 2019-6-25 22:35
硬币问题。。经典题。。。送分题。。。。

基础的硬币问题是无限取件，那楼主的答案没错啊，请问一下这样有限取件的解哪里可以学习一下？https://blog.csdn.net/qsyzb/article/details/26962753