[leetcode_55]Jump Game

从前往后一个一个标记会超时，后来想了下某些情况下复杂度是o(n^2)
但是从后往前标记，不一样，近似于o(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
public:
    void FindMin(int A[],int n,bool flag[]) {
        if(n <= 0)return;
        int min = 0xffff;
        for(int i = n-1;i >= 0;i--) {
            if(A[i] + i >= n) {
                flag[i] = true;
                if(min > i)
                    min = i;
            }
        }
        if(min == 0xffff || flag[0] == true)return;
        FindMin(A,min,flag);
    }
    bool canJump(int A[], int n) {
        bool * flag = new bool[n+1];
        if(n == 1)return true;
        for(int i = 0;i < n;i++) {
            flag[i] = false;
        }
        FindMin(A,n-1,flag);
        return flag[0];
    }
};