算法分析：跳跃游戏_跳跃游戏怎么最优解证明

1.问题描述

给定一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

2.1贪心算法

（1）题目分析：对于这个题目，刚开始想的是当前位置元素如果是3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？然后就立马想到了能不能够通过局部最优解去获得全局的最优解。
仔细考虑一下，其实跳几步无所谓，关键在于可跳的覆盖范围！不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。这个范围内，别管是怎么跳的，反正一定可以跳过来。那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点。
（2）**初步思路：**每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
局部最优推出全局最优。
图片的解释更为直观：

编码：

def canJump1(nums):
    cover = 0
    if len(nums) == 1: return True
    i = 0

    while i <= cover:
        cover = max(i + nums[i], cover)
        if cover >= len(nums) - 1: return True
        i += 1
    return False
a1 = [2, 3, 1, 1, 4]
a2 = [3, 2, 1, 0, 4]
print(canJump1(a1))
print(canJump1(a2))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

运行结果：

True
False
1
2

2.2动态规划

（1）题目分析：通过贪心算法求解之后，可以再尝试下有没有其他方法能够解决这个问题。可以逆向思维来看一下，如果我们倒着来求，倒数第二个位置的值只有大于等于1才可以访问到最后一个值，或者倒数第三个位置的值只有大于等于2才可以访问到最后一个值。
**（2）初步思路：**定义一个end变量，作为终点，最开始的终点是len - 1。能否到达终点,就看它的：
前一个位置的数是不是大于1
或者：前两个位置的数是不是大于2
或者：前三个位置的数是不是大于3
或者：……………………（类推）
也就是nums[i] >= end - i 。如果可以的话，那么表示到了这个位置就表示可以到达终点，所以我们把这个位置定为新终点。继续看它的前一个/两个/三个/……………………
最后遍历到0，如果0是新的终点，就表示0可以到len -1。
编码：

def canJump2(nums):
    length = len(nums)
    end = length - 1
    i =length - 2
    while(i >= 0):
        if(nums[i] >= end - i ):
            end = i
        i -= 1
    return end == 0

a1 = [2, 3, 1, 1, 4]
a2 = [3, 2, 1, 0, 4]
print(canJump2(a1))
print(canJump2(a2))```
运行结果：

```python
True
False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.两种算法对比

在本题里，贪心算法可以看作是自顶向下的求解过程，动态规划算法可以看作是自底向上的求解过程，两个算法的时间复杂度都是O(n)，空间复杂度也都是O(n)。如果真要探究哪个方法更好，需要根据输入的测试数据来看，如果测试数据大多都能到达终点，则使用贪心算法的效率会相对较高，因为贪心算法在确认可以访问到最后一个终点时，就可以立即返回True，而动态规划从后往前判断，需要把所有的点都遍历一遍，从而导致效率降低。