狗狗店面

一个很nice的九年狗家白人小哥。
题目是：一个Array，代表第i天航行

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

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

题荒废太久了，我留下了悔恨的泪水 T_T，求加米安慰。

多谢楼主提供思路
感觉对我来说dfs更直观一点
dfs(day, power)，代表从第day天开始，有power能量，最多跑多远
那么，dfs(day, power) = max(dfs(day + 1, power + 1) //当天休息
                                               dfs(day + 1, power - 1) + arr[day]) //当天不休息

ZhimingZou 发表于 2024-5-8 10:05
不太懂，如果休息加1， 那我一直休息， 不久最终可以去任何地方

能量上限是 k， 最多休息k天
每天可航行里程不同， 要挑选最合适休息 + 航行

不太懂，如果休息加1， 那我一直休息， 不久最终可以去任何地方

ZhimingZou 发表于 2024-5-8 22:05
不太懂，如果休息加1， 那我一直休息， 不久最终可以去任何地方

比如Arr[10， 0， 5， 30]， k= 2，代表每天能走的distance，如果你休息了当天时间也过了，天数有限。

dp存天数和能量到距离的mapping？然后正向loop

匿名用户 发表于 2024-5-8 23:19
dp存天数和能量到距离的mapping？然后正向loop

差不多，就是带能量条件的背包问题，二维DP存天数和能量。空间不确定能不能优化到一维。

这不是直接贪心找k个最大的值就完了么？
要是arr[i]不在k个最大里面就休息，在里面就航行。。

补充内容 (2024-05-09 02:00 +08:00):

又想了下，不是纯选k个最大的。。
比如到第i天(i>k)，除了选k个最大的，还能在剩下的(i-k)个元素继续选。。
可以拿一半的时间来休息，另一半的时间来航行。。
那么第i天的答案就是k+(i-k)//2个最大值的总和，可以用最小堆实现。。

lz 求问，几年yoe，面的什么level


recruiter linkedin上面找的你吗

23781095 发表于 2024-5-9 09:25
lz 求问，几年yoe，面的什么level

3年，L4，对的