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];
    }