@SomeBottleLeetcode每日一题 —— 1340. 跳跃游戏 V 中发帖

还有第五关?!( °ヮ° ) 

思路
最开始看到这题脑子里会想能不能用栈做,一看输入规模,好像 O(n^2) 时间复杂度也可以接受。看了一眼提示后顿悟了,这题可以用动态规划。
动态规划 dp[i] 表示从 i 下标开始能跳跃的次数。
问题来了,我从哪个地方开始、按什么顺序递推呢?
开始的地方应当不依赖于任何其他 dp 状态,符合这个要求的显然是最低的一个柱子,这样的地方 p 无法跳到其他任何地方,自然有 dp[p]=0 (只能访问自身,一次都跳不了)
递推的时候我们只关注一个地方 i 能跳到哪些更矮的地方,然后可以尝试从这些地方中跳跃次数最多的柱子上转移过来。因此递推顺序也是沿着柱子高度来的。

我们可以按照柱子高度对下标进行排序,顺着排序后的下标递推。

递推的过程中可以不断用 \max(\cdot) 更新最终结果。

思路
class Solution {
publi...