题解 | #几步可以从头跳到尾#

由于数组的长度为 10 ** 5, 双重循环会超时,利用 一维 dp, 设置 dp[i] 表示 跳至 i 阶时最小的步数, 则 dp[i] = dp[j] + 1, j < i and j 从距离 i 最远的点跳过来, 即 A[j] 在 A[j:i] 中最大(最接近 i); 初始 dp = [0] * n, 设置 j 为初始索引遍历 dp , 判断每个 i 是由哪个 j 转移过来 while A[j] + j < i 循环,得到对应的 j,最终遍历完 dp[n - 1] 为 最终解

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少需要跳跃几次能跳到末尾
# @param n int整型 数组A的长度
# @param A int整型一维数组 数组A
# @return int整型
#

class Solution:
    def Jump(self , n: int, A: List[int]) -> int:
        # write code here
        dp = [0 for _ in range(n)]
        s = 0
        for i in range(1, n):
            while A[s] + s < i:
                s += 1
            dp[i] = dp[s] + 1
        return dp[-1]