背景介绍
这是再次复习这道题目的遇到的问题
DP 状态
dp[i]
表示跳到i
,包括i
之后, 还剩余的跳跃步数.
dp[0]
表示起点, dp[0]=nums[0]
排除法
- dp 初始化过程没有问题
- 应该是dp 推导过程出现了问题
举个例子
输入
[3,2,1,0,4]
打印出来 dp数组
[3, 2, 1, 0, -1]
问题所在, 就是如果判断dp[i-1]
会有遗漏, 导致最后一个问题出错.
看看代码
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
# dp 算法求解
# dp[i] 表示到达 i 的时候, 剩余的长度
n = len(nums)
dp = [0]*n
## 初始值
dp[0] = nums[0]
for i in range(1,n):
if dp[i-1] == 0:
return False
dp[i] = max(dp[i-1],nums[i-1])-1
return True
网友评论