狗狗新鲜电话面试新题+题解？求加米

刚面完，感觉基本挂了，这题没见过。面试的时候觉得肯定是用DP, 但是那个transition 方程就是想不出来。

• Given a distance list(kilos), kilos= [1,1,10,30,20,40], and starting capacity k=1, you w
  您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  使用VIP即刻解锁阅读权限或查看其他获取积分的方式

  游客，您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  VIP即刻解锁阅读权限 或 查看其他获取积分的方式
  Unlock interview details and practice with AI
  Curated Interview Questions from Top Companies
  
  >
  
  这是我后来自己做的，不知道是不是最优解，请大牛指点。代码写的很乱，基本思想就是 dp[ii][j] = max(dp[i+1][j-1] + kilos[j], dp[i-1][j-1]).[i]
  1. <div><i>                     def maximum_kilos(kilos, k):
     
  2. </i></div><div><i>  n = len(kilos)
     
  3. </i></div><div><i>  dp = [[None]*n for i in range(n+k+1)]
     
  4. </i></div><div><i>  # initialize the first column
     
  5. </i></div><div><i>  dp[k][0] = 0
     
  6. </i></div><div><i>  dp[k-1][0] = kilos[0]
     
  7. </i></div><div><i>  for j in range(1, n):
     
  8. </i></div><div><i>    for i in range(n+k-1,-1,-1):
     
  9. </i></div><div><i>      # print(i,j)
     
  10. </i></div><div><i>      if i==0:
      
  11. </i></div><div><i>        if dp[i+1][j-1] is not None:
      
  12. </i></div><div><i>          dp[i][j] = dp[i+1][j-1]+ kilos[j]
      
  13. </i></div><div><i>      else:
      
  14. </i></div><div><i>        if dp[i-1][j-1] is None and dp[i][j-1] is None and dp[i+1][j-1] is None:
      
  15. </i></div><div><i>          pass
      
  16. </i></div><div><i>        elif dp[i+1][j-1] is None and dp[i][j-1] is None:
      
  17. </i></div><div><i>          dp[i][j] = dp[i-1][j-1]
      
  18. </i></div><div><i>        elif dp[i-1][j-1] is None and dp[i][j-1] is None:
      
  19. </i></div><div><i>          dp[i][j] = dp[i+1][j-1] + kilos[j]
      
  20. </i></div><div><i>        elif dp[i+1][j-1] is None and dp[i][j-1] is not None:
      
  21. </i></div><div><i>          dp[i][j] = dp[i-1][j-1]
      
  22. </i></div><div><i>        elif dp[i-1][j-1] is None and dp[i][j-1] is not None:
      
  23. </i></div><div><i>          dp[i][j] = dp[i+1][j-1]+ kilos[j]
      
  24. </i></div><div><i>        else:
      
  25. </i></div><div><i>          dp[i][j] = max(dp[i+1][j-1]+kilos[j], dp[i-1][j-1])
      
  26. </i></div><div><i>  print('dp after operation: {}'.format(dp))
      
  27. </i></div><div><i>  res= max([ dp[i][n-1] for i in range(k+n) if dp[i][n-1] is not None])
      
  28. </i></div><div><i>  return res
      
  29. </i></div><div><i>kilos=[0,0,20,30,40,50]
      
  30. </i></div><div><i>k=1
      
  31. </i></div><div><i>res = maximum_kilos(kilos,k)</i></div>

  复制代码
  [/i]

DFS => cache => top-down DP => bottom-up DP => 优化memory的 bottom-up DP 是比较可行的思路

没有必要直接最后一步做起。DP关键的是中间状态怎么表示，这道题的话是dp[i][k], 每天有2种选择。和上面帖子说的差不多。因为i +1 只会有 i访问到,所以memory usage可以降维度

您好！
本帖隐藏的内容需要积分高于 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

大概写了一下

1. def maxDistances(kilos, k):
   
2.     m = k+len(kilos)
   
3.     res = 0
   
4.     dp = [[0 for i in range(m)] for j in range(len(kilos))]
   
5.     dp[0][k-1] = kilos[0]
   
6.     for i in range(1, len(kilos)):
   
7.         for j in range(k+i+1):
   
8.             if k < j:
   
9.                 continue
   
10.             if j == 0:
    
11.                 dp[i][j] = dp[i-1][j+1]+kilos[i]
    
12.             elif j == i+k:
    
13.                 dp[i][j] = dp[i-1][j-1]
    
14.             else:
    
15.                 dp[i][j] = max(dp[i][j], dp[i-1][j-1], dp[i-1][j+1]+kilos[i])
    
16.             res = max(res, dp[i][j])
    
17.     for r in dp:
    
18.         print(r)
    
19.     return res
    
20. 
    
21. kilos = [1,1,10,20,30,20,40]
    
22. print(maxDistances(kilos, 1))

复制代码

感觉跟加油站的题很像 不同的是 每一天要看上一天的 k-1 和 k+1
https://leetcode.com/playground/PsYavY8H

请教下题目细节, 看半天没有理解题目, 我们是要求可以走的最远距离吗? 限制是天数吗? 没有找到限制条件...

24790955 发表于 2021-9-18 05:43
请教下题目细节, 看半天没有理解题目, 我们是要求可以走的最远距离吗? 限制是天数吗? 没有找到限制条件...

是的，就是要求最远距离，限制条件就是当你在某一天结束的时候，只有0 capacity，你只能选择休息来获得capacity.

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

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

zn88358800 发表于 2021-9-18 00:34
大概写了一下感觉跟加油站的题很像 不同的是 每一天要看上一天的 k-1 和 k+1
https://leetcode.com/playg ...

请教你说的加油站的题，具体是哪题？感觉有很多加油站的题。。

做决策拿最优解的问题, 一般我倾向于用递归+memoization, 转移只用想状态随决策怎么变就行了, 再考虑下basecase,  贴上个人的参考代码:

1. from functools import cache
   
2. def max_distance(kilos: List[int], start_cap: int = 1) -> int:
   
3.         @cache
   
4.         def max_dist_sub(day_i: int, cap: int) -> int:
   
5.                 if day_i == len(kilos):
   
6.                         return 0
   
7.                 if cap > 0:
   
8.                         move_on = max_dist_sub(day_i+1, cap-1) + kilos[day_i]
   
9.                 else:
   
10.                         move_on = 0
    
11.                 charge = max_dist_sub(day_i+1, cap+1)
    
12.                 return max(charge, move_on)
    
13.         return max_dist_sub(0, start_cap)
    
14. if __name__ == '__main__':
    
15.     kilos = [1,1,30,20,40]
    
16.     start_cap = 1
    
17.     print(max_distance(kilos, start_cap))

复制代码

1. 
   

复制代码

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

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