Leetcode -- Jump Game II

Exceed Time Limit

class Solution {  
 public:  
   int jump(int A[], int n) {  
     vector<int> dp(n, n - 1);  
     dp[n - 1] = 0;  
     for(int i = n - 2; i>=0; --i) {  
       if(A[i] + i >= n - 1) {  
         dp[i] = 1;  
       } else {  
         for(int j = A[i]; j > 0; --j) {  
         if(dp[i + j] + 1 < dp[i]) {  
           dp[i] = dp[i + j] + 1;  
           }  
          }  
       }  
     }  
     return dp[0];  
   }  
 };  

c.f. discussion

class Solution {  
 public:  
   int jump(int A[], int n) {  
     int ret =0, last = 0, curr = 0;  
     for(int i = 0; i < n; ++i) {  
       if(i > last) {  
         last = curr;  
         ret++;  
       }  
       curr = max(curr, i+A[i]);  
     }  
     return ret;  
   }  
 };