从前往后一个一个标记会超时,后来想了下 某些情况下复杂度是o(n^2)
但是从后往前标记,不一样,近似于o(n)
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]; } };