每日一题20201115（55. 跳跃游戏）

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