55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

  1. //最优 贪心算法，时间On，空间O1
  2. func canJump(nums []int) bool {
  3.     n := len(nums)
  4.     max_step := 0               //最远可到达的 步长，上一步的结果
  6.     for i := 0; i <n; i++ {
  7.         if max_step >= n-1 {        //说明此时就可以跳到尽头
  8.             return true
  9.         }
  11.         if max_step < i {           //说明当前的下标i，比上一步的步长远，到不了了
  12.             return false
  13.         }
  15.         max_step = max(max_step, nums[i] + i)   //常规情况，可跨过的，继续跳并记录步长
  16.     }
  18.     return false                        //遍历完了，还没跳出，就不可能了
  19. }
  21. func max(x,y int) int {
  22.     if x > y {
  23.         return x
  24.     }
  25.     return y
  26. }
//dp解法，时间为On^2，空间On
func canJump(nums []int) bool {
    n := len(nums)
    dp := make([]bool, n)

    dp[0] = true
    for i := 1; i < n; i++ {
        dp[i] = false

        for j := 0; j < i; j++ {
            if dp[j] && nums[j] +j >= i {        //当前点可跳跃，且步长 + 索引下标 》前一步的索引
                dp[i] = true                    // 如果之前的j节点可达，并且从此节点可以到跳到i  && 从前往后 可到达i
                break
            }
        }
    }
    return dp[n-1]
}