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

又写了下DP版本的:

1. public static int method(int[] kilos) {
   
2.         int n = kilos.length;
   
3.         // dp[day][capacity], and dp is distance at the end of day.
   
4.         int[][] dp = new int[n][n + 1];
   
5.         
   
6.         // Initilize dp
   
7.         for (int i = 0; i < n; i++)
   
8.             Arrays.fill(dp[i], Integer.MIN_VALUE);
   
9.         dp[0][2] = 0; // rest on day1
   
10.         dp[0][0] = kilos[0]; // move on day1
    
11.       
    
12.        //  for dp[i][j], if rest: dp[i - 1][j -1]  move: dp[i - 1][j + 1] + kilos[i]
    
13.         for (int i = 1; i < n; i++) {
    
14.             for (int j = 0; j <= n; j++) {
    
15.                 int move = (j == n) ? Integer.MIN_VALUE : dp[i - 1][j + 1] + kilos[i];
    
16.                 int rest = (j == 0) ? Integer.MIN_VALUE : dp[i - 1][j - 1];
    
17.                 dp[i][j] = Math.max(move, rest);
    
18.             }
    
19.         }
    
20.       
    
21.         int maxRes = 0;
    
22.         for (int j = 0; j <= n; j++) { //capacity
    
23.             maxRes = Math.max(maxRes, dp[n - 1][j]);
    
24.         }
    
25.         return maxRes;
    
26.     }

复制代码

"you can get 2 day rest and still get k=3, but the final res is still 90." 请问这个是怎么取得？我的理解是当天结束时capacity必须大于0，如果你拿到了今天的kilo，但是当天结束时capacity为0，则不行，因而必须在今天rest。这样理解对吗？

感觉我理解题目有问题，我来做的话就是每次都拿最大值，cap没了就歇一天，最简单的贪心就行了。或者n = (k+1)/2算出能取多少次，然后linear search找出前n大的数。

lllxin37 发表于 2021-9-18 21:44
DFS => cache => top-down DP => bottom-up DP => 优化memory的 bottom-up DP 是比较可行的思路

没有必 ...

非常有建设性的建议。感谢

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

lllxin37 发表于 2021-09-28 11:05:47
没有本质区别。不过要注意的是如果dfs + memo ==> bottom-up DP的话，要比较注意的是dp状态和状态转化方程。所以需要的话尽量在dfs + memo的时候定义好 clear 的DP

了解了，感谢！

wenlongdaxia 发表于 2021-9-18 08:09
是的，就是要求最远距离，限制条件就是当你在某一天结束的时候，只有0 capacity，你只能选择休息来获得ca ...

那就无限期休息，攒够capacity之后所有的distance都能拿
肯定还有其他限制条件吧？

匿名者 发表于 2021-11-17 22:13
那就无限期休息，攒够capacity之后所有的distance都能拿
肯定还有其他限制条件吧？

不对啊，那你挑什么时候休息呢？万一你挑的前面休息时间正好distance值很大呢