<p>You are given a <strong>0-indexed</strong> array of integers <code>nums</code> of length <code>n</code>. You are initially positioned at <code>nums[0]</code>.</p>

<p>Each element <code>nums[i]</code> represents the maximum length of a forward jump from index <code>i</code>. In other words, if you are at <code>nums[i]</code>, you can jump to any <code>nums[i + j]</code> where:</p>

<ul>
	<li><code>0 &lt;= j &lt;= nums[i]</code> and</li>
	<li><code>i + j &lt; n</code></li>
</ul>

<p>Return <em>the minimum number of jumps to reach </em><code>nums[n - 1]</code>. The test cases are generated such that you can reach <code>nums[n - 1]</code>.</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> 2
<strong>Explanation:</strong> The minimum number of jumps to reach the last index is 2. 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 = [2,3,0,1,4]
<strong>Output:</strong> 2
</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;= 1000</code></li>
	<li>It&#39;s guaranteed that you can reach <code>nums[n - 1]</code>.</li>
</ul>

class Solution:
    # brute-force
    def minjump(self,nums: List[int], idx):
        if idx>=len(nums)-1:
            return 0
        count=10001
        for i in range(idx+1,idx+nums[idx]+1):
            count=min(count,1+self.minjump(nums,i))
        return count

    # recursive dp
    def minjumpdp(self,nums: List[int],dp: List[int], idx):
        if idx>=len(nums)-1:
            return 0
        if dp[idx]<1001:
            return dp[idx]
        count=1001
        for i in range(idx+1,idx+nums[idx]+1):
            dp[idx]=min(dp[idx],1+self.minjumpdp(nums,dp,i))
        return dp[idx]


    def min_jump(self,dp,nums, index):

        if index>=len(nums)-1:
            return 0
        if dp[index]!=100000:
            return dp[index]
        step = 100000
        for i in range(1,nums[index]+1):
            x = self.min_jump(dp,nums,index+i)+1
            step = min(step,x)
        dp[index]=step
        return step


    def jump(self, nums: List[int]) -> int:
        
        dp = [ 100000 for _ in range(0,len(nums))]
        res =self.min_jump(dp,nums, 0)

        return res



















        # if len(nums)<=1:
        #     return 0
        # for i in range(1,len(nums)):
        #     nums[i]=max(nums[i]+i,nums[i-1])
        
        # i=0
        # count=0
        # while i<len(nums)-1:
        #     count+=1
        #     i=nums[i]
            
        # return count

        # brute-force
        # res=self.minjump(nums,0)

        # recursive dp
        # dp = [10001 for i in range(0,len(nums))]
        # res=self.minjumpdp(nums,dp,0)
        # return res

        # iterative dp
        # dp = [10001 for i in range(0,len(nums))]

        # dp[len(nums)-1]=0

        # for i in range(len(nums)-2,-1,-1):
        #     for j in range(i+1,i+nums[i]+1):
        #         dp[i]=min(dp[i],1+dp[min(len(nums)-1,j)])

        # return dp[0]

        # greedy BFS
        x=0
        count=0
        i=0
        mx=0;mxidx=0

        while mxidx<len(nums)-1 :
            mx=max(mx,i+nums[i])
            if(i==mxidx):
                mxidx=mx
                count+=1
            i+=1
        return count




19700