【LeetCode】Jump Game (1维动态规划 + 线性扫描)

【LeetCode】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.

java code : 这题初看用DP的思路很清晰： 设DP[i] := 从第 i 个位置开始能否到底最后一个位置，那么转移方程很好写

  dp[A.length - 1] = true; 看代码吧，不过会超时，因为复杂度是O（n^2）

class Solution {public:    bool canJump(int A[], int n) {        // IMPORTANT: Please reset any member data you declared, as        // the same Solution instance will be reused for each test case.    int i = 0;    while( i < n-1)    {        if( A[i] == 0)            return false;        i += A[i];      }    return i >= n-1;    }    };

leetcode 的数据还是有点弱。