[leetcode] Jump Game

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.

思路：

动态规划。改变现有数组，使更改后的A[i]表示第在第i个位置所能前进的最大距离，如果某个点的最大距离是0，那么肯定无法到达终点。

题解：

class Solution {
public:
    bool canJump(int A[], int n) {
        if(n==0 || n==1)
            return true;
        if(A[0]==0)
            return false;
        for(int i=1;i<n;i++) {
            A[i] = max(A[i], A[i-1]-1);
            if(A[i]==0 && i!=n-1)
                return false;
        }
        return true;
    }
};

View Code

[leetcode] Jump Game

原文：http://www.cnblogs.com/jiasaidongqi/p/4184459.html