[leetcode_55]Jump Game

Marking from front to back one by one will time out. After some thought, in certain cases the complexity is O(n^2).
However, marking from back to front is different – it is approximately 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];
    }
};