# Jump Game

### 描述​

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

### 分析​

$f[i] = max(f[i-1], A[i-1])-1, i > 0$

### 代码 1​

// Jump Game// 思路1，时间复杂度O(n)，空间复杂度O(1)public class Solution {    public boolean canJump(int[] nums) {        int reach = 1; // 最右能跳到哪里        for (int i = 0; i < reach && reach < nums.length; ++i)            reach = Math.max(reach,  i + 1 + nums[i]);        return reach >= nums.length;    }}

### 代码 2​

// Jump Game// 思路2，时间复杂度O(n)，空间复杂度O(1)public class Solution {    public boolean canJump(int[] nums) {        if (nums.length == 0) return true;        // 逆向下楼梯，最左能下降到第几层        int left_most = nums.length - 1;        for (int i = nums.length - 2; i >= 0; --i)            if (i + nums[i] >= left_most)                left_most = i;        return left_most == 0;    }}

### 代码 3​

// Jump Game// 思路三，动规，时间复杂度O(n)，空间复杂度O(n)public class Solution {    public boolean canJump(int[] nums) {        int[] f = new int[nums.length];        for (int i = 1; i < nums.length; i++) {            f[i] = Math.max(f[i - 1], nums[i - 1]) - 1;            if (f[i] < 0) return false;;        }        return f[nums.length - 1] >= 0;    }}