55. jump game

一个数组，上面的数字代表在每个位置上可以前进的步数，判断能否跳到最后一位

思路：动态规划，但并不需要一个dp数组来记录, 维护一个step变量，不断向前推进, 每个位置上可前进的最大步数等于前面剩余的步数和nums[i]中较大的一个数值

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        # 6 star, no idea. 
        step = nums[0]
        for i in range(1, len(nums)):
            if step > 0:
                step -= 1
                step = max(nums[i], step) # 在当前索引上可以前进的步数
            else:
                return False
        return True

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 6 star, 用一个与nums等长的切片canArrive记录每个索引能否被跳到，从左到右遍历nums,根据每个索引上的步数更新canArrive上对应索引的值
//最后判断canArrive上最后一位的值是否为1
func canJump(nums []int) bool {
	var steps int
	canArrive := make([]int, len(nums))
	canArrive[0] = 1
	length := len(nums)
	index := 0
	for index < length && canArrive[index] == 1 {
		steps = nums[index]
		for idx:=1; idx<=steps;idx++{
			if index + idx >= length - 1 {return true}
			canArrive[index+idx] = 1
		}
		index += 1
	}
	return canArrive[length-1] == 1

}