问一道狗家onsite的DP题 不太懂

Leetcode上看到的最近newgrad的onsite题目，类似于knapsack，实在想不出来这个DP关系应该怎么写，有没有大神来看看解析一下

Given digits 1-9 with each digit associated with a value. Now we have a wall that needs to be painted with those digits and each digit painted requires the value volume, you need to form the largest number possible from this. Given that the sum of the volume of the number is equal to the wall volume.

Input:
1 2 3 4 5 6 7 8 9
1 3 1 5 6 7 2 5 2
wall volume: 5
Output: 33333

（原贴地址：https://leetcode.com/discuss/int ... rad-feb-2020-reject）

Actuant 发表于 2020-3-14 02:59
我是这么想的，dp代表用volume i的时候的答案，i可以取0, 1, ..., volume，最后返回dp的最后一位。

构建 ...

能不能直接算出最后答案是几位数？例如五位数必然比四位数大，所以选择volume最小的digit，volume相同时选择更大的数字。

我是这么想的，dp[i]代表用volume i的时候的答案，i可以取0, 1, ..., volume，最后返回dp的最后一位。

构建一个hashmap, 存下来每个vol对应的最大value是多少。对于1 3 1 5 6 7 2 5 2来说，dict[1] = 3

转移方程是：dp[i] = max(dp[i-j] * 10 + dict[j]), for j = 1, 2, ..., min(i, 9)，这里假设每位最多是9

下面是code, time和space complexity是O(n)，可能有大神有更好的解法：

1. 
   
2. import collections
   
3. 
   
4. class Solution:
   
5.         def find_largest_num(self, nums, volume):
   
6.                
   
7.                 vol_dict = {}
   
8.                 for i, num in enumerate(nums):
   
9.                         vol_dict[num] = i + 1
   
10. 
    
11.                 dp = [0] * (volume + 1)
    
12. 
    
13.                 for i in range(1, volume + 1):
    
14.                         for j in range(1, min(i + 1, 10)):
    
15.                                 if j not in vol_dict:
    
16.                                         continue
    
17.                                 dp[i] = max(dp[i], dp[i - j] * 10 + vol_dict[j])
    
18. 
    
19.                 return dp[-1]
    
20. 
    
21. 
    
22. if __name__ == '__main__':
    
23.         s = Solution()
    
24.         nums = [1, 3, 1, 5, 6, 7, 2, 5, 2]
    
25.         print(s.find_largest_num(nums, 5))
    

复制代码

首先要尽可能多选digits，在确定了digits数量后，要使得高位尽可能大。

dp[i]表示volume为i时最多可以选多少个数。这个类似背包的思路跑一下就可以算出来。

在跑的时候，对于每一个dp[i]，需要记录是选择了哪个digit转移过来的。

这里可能有多个状态可以转移到dp[i]，选择一个可以让当前digit最大的状态转移就可以了。（因为高位digit要尽可能大）

这样从dp[volume]倒推回去，把每步转移的digit连起来，倒过来就是答案了。

随手yy的，欢迎指正orz

Actuant 发表于 2020-3-13 13:59
我是这么想的，dp代表用volume i的时候的答案，i可以取0, 1, ..., volume，最后返回dp的最后一位。

构建 ...

这个解法很好，我觉得一个可能的follow up是，如果不是用的不是python，这个方程dp = max(dp[i-j] * 10 + dict[j])直接用 ，如果volume很大的话，可能会integer overflow.

Actuant 发表于 2020-3-14 02:59
我是这么想的，dp代表用volume i的时候的答案，i可以取0, 1, ..., volume，最后返回dp的最后一位。

构建 ...

转移的时候也可以加到前面吧，感觉要求一个max(pow(10, dp[i-j]的位数-1) * vol_dict[j], dp[i - j] * 10 + vol_dict[j])

没看懂这个题目。 谁可以认真解释下这个Input output呢？
Input:
1 2 3 4 5 6 7 8 9
1 3 1 5 6 7 2 5 2
wall volume: 5
Output: 33333

david_smith 发表于 2020-3-16 22:03
没看懂这个题目。 谁可以认真解释下这个Input output呢？
Input:
1 2 3 4 5 6 7 8 9

这个input第一行是数字，第二行是数字对应的volume
就是数字1的volume是1，数字2的volume是3，数字3的volume是1，etc

bydstand 发表于 2020-3-16 11:51
能不能直接算出最后答案是几位数？例如五位数必然比四位数大，所以选择volume最小的digit，volume相同时 ...

我也感觉没太看明白，既然每位数字对应的值只是从1-9，那么只需要找到1对应的最大值，需要的wall volume是几就是由这个最大值构建成的几位数是不是就可以了？毕竟位数大一定比位数小的大。不过我的理解可能有问题，不会这么直接吧。