LeetCode 45. Jump Game II(DP）

DP(动态规划）

1.状态定义

f[j]:到 j的最小次数

2.状态初始化

f[0] = 0 其余=正无穷

3,转移方程

第i+j个位置只能有第i个位置跳过来

f[i + j] = min(f[i+j],f[i] + 1) 

其中：

i：起跳位置
j：跳的步数 (0<=j<=nums[i])

代码 (Python)

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        f = [inf for i in range(20 ** 4 + 10)]
        f[0] = 0
        for i in range(n):
            for j in range(nums[i] + 1):
                f[i + j] = min(f[i + j],f[i] + 1)
        return f[n - 1]