55. 跳跃游戏
image.png
方法一: 贪心算法
维护一个能跳到最大距离的变量,遍历数组,每次更新这个变量。可以遍历完成后比较这个值与数组的长度-1,也可以每次遍历的时候判断是否大于了数组长度-1,如果是则直接return
class Solution: def canJump(self, nums: List[int]) -> bool: max_distance = 0 for i, n in enumerate(nums): # 当i = 0的时候,最大距离肯定为0,i > max_distance是因为第i个索引的位置都跳不到就更不可能跳到最后一个了,这时候跳出循环 if i > max_distance and i != 0: break if n + i > max_distance: max_distance = n + i # 最后判断是否大于等于数组长度-1(也就是能达到最后一个元素) return max_distance >= len(nums) - 1
image.png
方法二 动态规划(一开始的思路,Python直接超时, 可以上go)
思路也很简单,类似于跳台阶,维护一个dp数组,看达到最后一个台阶的方式有多少种,并判断他是否大于0.
func canJump(nums []int) bool { if len(nums) == 0 { return false } result := make([]int, len(nums), len(nums)) for i, _ := range nums { if i == 0 { result[i] = 1 continue } for j:=0; j<i; j++ { if nums[j] >= i-j { result[i] += result[j] } } } return result[len(nums)-1] > 0 }
image.png