leetcode || 55、Jump Game

leetcode || 55、Jump Game

problem：

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.

thinking：

（1）剛開始想到DFS，對每一個到達的結點作深搜，但是由於邊界條件較少，時間復雜度會急劇膨脹，不太可行

（2）另外一種方法是采用貪心策略，之前一道Jump Game 題目，求步數的也是采用貪心。思路是，采用A[base+step]+step的加權方式來衡量每一次選擇的優劣，判斷當跳到第一個0處，能否到達或者超過數組最後一個數字。

這裡假設成立的是：每次跳躍選擇往最遠處跳躍，如果最後能夠跳到數組最後一位或者最後一位之後，那麼一定存在一種跳躍方式正好跳到最後一位上

這個假設很容易證明是成立的，因為最後一步跳躍可以選擇0~step之間的任意一步

code：

class Solution {
public:
    bool canJump(int A[], int n) {
        if(n==1)
            return true;
        int index=0;
        int _max=0;
        while(index=n-1)
                return true;
            if(A[index]==0 )
            {
                if(_max=tmp)
                    {
                        tmp=A[index+i]+i;
                        flag=i;
                    }
            }
           index+=flag;
           _max=A[index]+index;
        }
        
    }
};