跳跃游戏

来源Leetcode第55题跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。
示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

回溯

来自题解

模拟从第一个位置跳到最后位置的所有方案。从第一个位置开始，模拟所有可以跳到的位置，然后从当前位置重复上述操作，当没有办法继续跳的时候，就回溯。
缺点是会超时。

public class Solution {
    public boolean canJumpFromPosition(int position, int[] nums) {
        if (position == nums.length - 1) {
            return true;
        }

        int furthestJump = Math.min(position + nums[position], nums.length - 1);
		//列举所有可能的跳法
        for (int nextPosition = furthestJump; nextPosition > position; nextPosition--) {
            if (canJumpFromPosition(nextPosition, nums)) {
                return true;
            }
        }

        return false;
    }

    public boolean canJump(int[] nums) {
        return canJumpFromPosition(0, nums);
    }
}

自顶向下的动态规划

来自题解

定义：能到达最后一个位置的坐标为好坐标，反之为坏坐标。
自顶向下的动态规划可以理解成回溯法的一种优化。我们发现当一个坐标已经被确定为好 / 坏之后，结果就不会改变了，这意味着我们可以记录这个结果，每次不用重新计算。

因此，对于数组中的每个位置，我们记录当前坐标是好 / 坏，记录在数组 memo 中，定义元素取值为 GOOD ，BAD，UNKNOWN。这种方法被称为记忆化。

步骤：

• 初始化 memo 的所有元素为 UNKNOWN，除了最后一个显然是 GOOD （自己一定可以跳到自己）
• 优化递归算法，每步回溯前先检查这个位置是否计算过（当前值为：GOOD / BAD）
  • 如果已知直接返回结果 True / False
  • 否则按照之前的回溯步骤计算
• 计算完毕后，将结果存入memo表中

int [] memo; // 用0，1，-1三态来定义未知，好与坏
 public  boolean canJump(int position , int[] nums){
     //如果当前位置并非位置，返回状态是否是好位置
     if (memo[position] != 0)
         return memo[position] == 1 ? true : false;

     int furthestJump = Math.min(position + nums[position],nums.length - 1);
     //如果能到最后位置，则为好位置
     for(int nextPosition = position + 1 ; nextPosition <= furthestJump ; nextPosition++){
         if(canJump(nextPosition,nums)){
             memo[position] = 1;
             return true;
         }
     }
     //否则记为坏位置
     memo[position] = -1;
     return false;
 }

 public boolean canJump(int[] nums) {
     memo = new int[nums.length];
     memo[nums.length - 1] = 1;
     return canJump(0 , nums);
 }

自底向上的动态规划

来自题解

自底向上和自顶向下动态规划的区别就是消除了回溯，在实际使用中，自底向下的方法有更好的时间效率因为我们不再需要栈空间，可以节省很多缓存开销。更重要的事，这可以让之后更有优化的空间。回溯通常是通过反转动态规划的步骤来实现的。

这是由于我们每次只会向右跳动，意味着如果我们从右边开始动态规划，每次查询右边节点的信息，都是已经计算过了的，不再需要额外的递归开销，因为我们每次在 memo 表中都可以找到结果。

enum Index {
    GOOD, BAD, UNKNOWN
}

public class Solution {
    public boolean canJump(int[] nums) {
        Index[] memo = new Index[nums.length];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.length - 1] = Index.GOOD;

        for (int i = nums.length - 2; i >= 0; i--) {
            int furthestJump = Math.min(i + nums[i], nums.length - 1);
            for (int j = i + 1; j <= furthestJump; j++) {
                if (memo[j] == Index.GOOD) {
                    memo[i] = Index.GOOD;
                    break;
                }
            }
        }

        return memo[0] == Index.GOOD;
    }
}

自顶向下的贪心

当我们把代码改成自底向上的模式，我们会有一个重要的发现，从某个位置出发，我们只需要找到第一个标记为 GOOD 的坐标（由跳出循环的条件可得），也就是说找到最左边的那个坐标。如果我们用一个单独的变量来记录最左边的 GOOD 位置，我们就可以避免搜索整个数组，进而可以省略整个 memo 数组。

从右向左迭代，对于每个节点我们检查是否存在一步跳跃可以到达 GOOD 的位置（currPosition + nums[currPosition] >= leftmostGoodIndex）。如果可以到达，当前位置也标记为 GOOD ，同时，这个位置将成为新的最左边的 GOOD 位置，一直重复到数组的开头，如果第一个坐标标记为 GOOD 意味着可以从第一个位置跳到最后的位置。

public boolean canJump(int[] nums) {
    int lastPos = nums.length - 1;
    for (int i = nums.length - 1; i >= 0; i--) {
        if (i + nums[i] >= lastPos) {
            lastPos = i;
        }
    }
    return lastPos == 0;
}

自底向上的贪心

从第0个位置出发，如果当前位置可跳跃距离为n，意味着接下来n个位置都可以作为跳跃点。
接下来对这n个格子都跳一次，更新能到达的最远距离，如果能到最后位置，则返回true。

public boolean canJump(int[] nums) {
    int maxLength = 0 ;
    for(int i = 0 ; i < nums.length ; i++){
        if(i > maxLength) return false;
        maxLength = Math.max(maxLength,i + nums[i]);
        if(maxLength >= nums.length - 1)
            //如果最远可到达的位置大于数组长度，则可到达
            return  true;
    }
    return false;
}