lintcode116. 跳跃游戏 深度搜索

给出一个非负整数数组，你最初定位在数组的第一个位置。

数组中的每个元素代表你在那个位置可以跳跃的最大长度。

判断你是否能到达数组的最后一个位置。

样例
样例 1

输入 : [2,3,1,1,4]
输出 : true
样例 2

输入 : [3,2,1,0,4]
输出 : false
注意事项
这个问题有两个方法，一个是贪心和 动态规划。

贪心方法时间复杂度为O（N）。

动态规划方法的时间复杂度为为O（n^2）。

我们手动设置小型数据集，使大家可以通过测试的两种方式。这仅仅是为了让大家学会如何使用动态规划的方式解决此问题。如果您用动态规划的方式完成它，你可以尝试贪心法，以使其再次通过一次。
           

深度搜索：从第一个开始，对其中的每一步进行检索，如果可以到达最后一步，则正确

class Solution {
public:
    /**
     * @param A: A list of integers
     * @return: A boolean
     */
    bool canJump(vector<int> &A) {
        // write your code here
        /*bool judge=false;
        DFS(A,0,judge);
        return judge;*/
        
    }
    void DFS(vector<int> &A,int index,bool &judge)
    {
        if(index==A.size()-1) {judge=true;return;}
        if(index>=A.size()||A[index]==0) {judge=false;return;}
        for (int i = 1; i <= A[index]; i++) {
            /* code */
            DFS(A,index+i,judge);
            if(judge) return;
        }
    }
};
           

方法二：设置一个判断数组，对每一个可以到达的地方赋值为true，看最后一个数是否为true即可

bool canJump(vector<int> &A) {
        // write your code here
        vector<bool>result(A.size(),false);
        result[0]=true;
        for (int i = 0; i < A.size(); i++) {
            /* code */
            if(result[i])
            {
                for (int j = 1; j <= A[i]; j++) {
                    /* code */
                    result[i+j]=true;
                }
            }
        }
        return result[result.size()-1];
    }