狗狗店面

why 2d dp? 1d dp with dp[i]=max length with i energy left should be enough?

谢谢分享 祝lz一切顺利 !

谢谢分享 祝lz一切顺利！

tofel18 发表于 2024-6-13 09:27
why 2d dp? 1d dp with dp=max length with i energy left should be enough?

应该不行吧？

如果休息 能量会+1，因此dp[i]会依赖dp[i+1]和dp[i-1]。

如果休息能量不变，可以改成一维。

不知道这么理解有没有问题

能请问选择的编程语言吗

LZ 的语言表达能力。。。 有谁把题看懂了吗？

EbyccoCheng 发表于 2024-05-08 09:41:30
多谢楼主提供思路
感觉对我来说dfs更直观一点
dfs(day, power)，代表从第day天开始，有power能量，最多跑多远

我也很难一下子抽象出dp的状态转移，写recur+memo再推导出状态转移对我来说相对好想一些

dp[j] = max(dp[i-1][j-1], dp[i-1][j+1] + arr[i]) (注意边界情况)

这题如果没有上限为k的条件可以用greedy + heap， O(n log n)