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

DP的做法，代码比较糙，但是能跑对，目前还没有遇到不正确的case，欢迎各位同学指正。

1. import sys
   
2. 
   
3. class Solution:
   
4.     def coin_change(self, coins, nums, amount):
   
5.         # 一共有多少个硬币，给硬币编号
   
6.         total = 0
   
7.         for n in nums:
   
8.             total += n
   
9. 
   
10.         # 先初始化成 一维数组
    
11.         dp = [0] * total
    
12. 
    
13.         index = 0
    
14.         while index < total:
    
15.             dp[index] = [0] + [sys.maxsize] * amount
    
16.             index += 1
    
17. 
    
18.         money = []
    
19.         for i, c in enumerate(coins):
    
20.             money += [c] * nums[i]
    
21. 
    
22.         # dp[i][j] 是说，编号是 i 的硬币可以参与 (只有两个选择，用上这个硬币，或者不用) 的时候， j 这么多钱最少要多少硬币
    
23.         for i in range(0, total):
    
24.             for j in range(0, amount + 1):
    
25.                 if j - money[i] == 0:
    
26.                     dp[i][j] = 1
    
27.                 elif j - money[i] < 0:
    
28.                     if (i >= 1):
    
29.                         dp[i][j] = dp[i - 1][j]
    
30.                 else:
    
31.                     # 第一个硬币，没有更前面的一个硬币了，不用考虑，就是 sys.maxsize, 初始化的时候设置好了
    
32.                     # 而且在一直用到前一个硬币的情况下，扣去现在考虑的这枚硬币的面值之后，还能有解决方案的时候
    
33.                     # 就可以考虑哪一个方案用的硬币更少了
    
34.                     if i != 0:
    
35.                         if dp[i - 1][j - money[i]] != sys.maxsize:
    
36.                             dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - money[i]] + 1)
    
37.                         else:
    
38.                             dp[i][j] = dp[i - 1][j]
    
39. 
    
40.         return dp[total - 1][amount] if dp[total - 1][amount] != sys.maxsize else -1
    
41. 
    
42. 
    
43. if __name__ == "__main__":
    
44.     print(Solution().coin_change([1, 2, 5], [1, 1, 1], 8))
    
45.     print(Solution().coin_change([1, 2, 5], [1, 8, 3], 16))
    
46.     print(Solution().coin_change([7, 2, 5], [1, 5, 1], 8))
    
47.     print(Solution().coin_change([1, 2, 5, 6], [1, 1, 1, 1], 8))
    
48.     print(Solution().coin_change([7, 2, 5, 10], [2, 1, 1, 1], 14))
    
49.     print(Solution().coin_change([7, 2, 5, 10], [1, 2, 1, 1], 14))

复制代码

这有个网上的代码，是c++的

https://ideone.com/w4Z7Ul

请问LZ面的什么级别的职位？

whodatj 发表于 2019-7-16 13:11
请问LZ面的什么级别的职位？

New Graduate的统招