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

这道题最naive的想法是递归。

example1:

A[0] covers A[1]&A[2]

A[1] covers A[2]&A[3]&A[4]  true

example2:

A[0] covers A[1]&A[2]&A[3]

A[1] covers A[2]&A[3]

A[2] covers A[3]

A[3]  covers nothing

false

为了去除重复计算，可以建立一个map，将已经确认无解的index存起来。每次开始递归时先判断一下在不在map中。

如果仅仅是这样的话，是TLE，通不过测试的。

现在的想法是怎样把递归去掉。

这种类似尾递归的做法是：

A[0]依赖于A[0+jump1]依赖于A[0+jump1+jump2]…然后逐层返回结果

能否改成：

0+jump1+jump2+…然后与n-1进行比较？

答案是可以的，一开始没想出来，看了一下Discussion里的，很巧妙，把当前最大cover范围max作为for循环的终止条件，并不断更新max

参考这样的想法，我的实现如下：

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

【LeetCode】Jump Game,布布扣,bubuko.com

【LeetCode】Jump Game

原文：http://www.cnblogs.com/ganganloveu/p/3707893.html