Skip to main content

55. Jump Game

分析

两种写法
1. DFS 搜索 注意需要加缓存 n^2
2. 从终点开始往回找,感觉挺巧妙的

题解

DFS

func canJump(nums []int) bool {
return dfs(0, nums, make([]bool, len(nums)))
}

func dfs(index int, nums []int, visited []bool) bool {
if index == len(nums) - 1 {
return true
}
if visited[index] {
return false
}
visited[index] = true
maxStep := nums[index]
for i := 1; i <= maxStep; i++ {
// 下一步如果超过了,后面都不用尝试了
nextStep := index + i
if nextStep >= len(nums) {
break
}
flag := dfs(nextStep, nums, visited)
if flag {
return true
}
}
return false
}

贪心

func canJump(nums []int) bool {
goal := len(nums) - 1

for i := goal - 1; i >= 0; i-- {
// 如过能够得着 goal, 就移动 goal
if nums[i] + i >= goal {
goal = i
}
}

return goal == 0
}