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]
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » LeetCode 45. Jump Game II(DP)
发表评论 取消回复