<p>You are given an integer array <code>nums</code>. You are initially positioned at the array&#39;s <strong>first index</strong>, and each element in the array represents your maximum jump length at that position.</p>

<p>Return <code>true</code><em> if you can reach the last index, or </em><code>false</code><em> otherwise</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,3,1,1,4]
<strong>Output:</strong> true
<strong>Explanation:</strong> Jump 1 step from index 0 to 1, then 3 steps to the last index.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,2,1,0,4]
<strong>Output:</strong> false
<strong>Explanation:</strong> You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:
    
      
    bool canJump(vector<int>& nums) {
         int n = nums.size();
        
        
        vector<int> t(n, false);
        //t[i] = True means, you can reach index i
        
        t[0] = true; //Already at starting index
        
        for(int i = 1; i<n; i++) {
            for(int j = i-1; j>=0; j--) {
                if(j + nums[j] >= i && t[j]) { //here t[j] == true means you should be able to reach j also, 
                                               //then only you can plan to jump(j+nums[i])  from this jth index
                    t[i] = true;
                    break;
                }
            }
        }
        
        
        return t[n-1];
       
        
        
    }
};
//memoization
// int t[10001];
//     bool solve(vector<int>& nums, int n, int idx) {
//         if(idx == n-1)
//             return true;
        
//         if(t[idx] != -1)
//             return t[idx];
        
//         for(int i = 1; i <= nums[idx]; i++) {
//             if(solve(nums, n, idx+i))
//                 return t[idx] = true;
//         }
    
//         return t[idx] = false;
//     }
//     bool canJump(vector<int>& nums) {
//          int n = nums.size();
//         memset(t, -1, sizeof(t));
//         return solve(nums, n, 0);
        
        
//     }
// };
// bool canJump(vector<int>& nums) {
//         int maxidx=0;
        
        
//         for(int i=0;i<nums.size();i++){
//             if(i>maxidx) return false;
//             maxidx=max(maxidx,i+nums[i]);
//         }
//         return true;
        
//     }
53400