1.題目描述（難度Hard）
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: 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.
Note:
You can assume that you can always reach the last index.
2.題目分析
題目要求：給你一個(gè)數(shù)組，數(shù)組中每位保存的是它可以向后走的最大步長，求最短可以走到數(shù)組末尾的步數(shù)。假設(shè)我們開始在初始的位置扯旷，即我們走0步就可以到達(dá)初始位置數(shù)組的index=0的地方。
解題思路：
這種題目，首先我想到的是樹的廣度優(yōu)先遍歷备禀，從前往后遍歷數(shù)組男翰，每個(gè)index都可以有一個(gè)子樹，如果遇到子樹可以到達(dá)數(shù)組尾部鹏倘，則范圍當(dāng)前的步數(shù)镜粤，后來發(fā)現(xiàn)，這個(gè)思路想復(fù)雜了。因?yàn)檫@種思路會(huì)有很多重復(fù)的計(jì)算朱灿，計(jì)算過的index向后會(huì)有很多重復(fù)缀去。如果數(shù)組比較大的會(huì)池户，內(nèi)存也會(huì)危險(xiǎn)。
其實(shí)，依舊是廣度優(yōu)先遍歷，只是每次我們有個(gè)范圍，[begin, end],我們每走一步左胞，就知道我們下一步的范圍俭嘁，我們只需要把當(dāng)前范圍內(nèi)所能達(dá)到的最短最長處近她，作為下一個(gè)探索區(qū)間的范圍即可泳桦。
每次向前走一個(gè)區(qū)間谒府，我們都步數(shù)+1
當(dāng)在某個(gè)區(qū)間能達(dá)到數(shù)組尾部時(shí)，我們返回當(dāng)前的步數(shù)即可惦蚊。
3.解題過程
Begin（算法開始）
輸入 數(shù)組nums
計(jì)算數(shù)組的長度N蹦锋，初始化起始位置begin和結(jié)束位置end都為0莉掂，當(dāng)前走的步數(shù)steps=0
當(dāng)結(jié)束位置end<N-1執(zhí)行循環(huán)
當(dāng)前步數(shù)steps+=1
maxIndex = end
for i in range(begin,end+1)
(因?yàn)閞ange是[)所以厘唾，最后一個(gè)要比實(shí)際可以達(dá)到的+1)
gofar = i+nums[i]#當(dāng)前位置可以達(dá)到最遠(yuǎn)的index
如果gofar>=N-1: return 當(dāng)前steps
如果gofar>maxIndex:當(dāng)前最大的maxIndex= gofar
上一輪循環(huán)完畢鹤树，我們重置begin,end = end+1,maxIndex
返回 steps//這個(gè)其實(shí)是留給上來就達(dá)到數(shù)組尾部的情況的
End （算法結(jié)束）
具體代碼（python）已對(duì)應(yīng)實(shí)現(xiàn)，但是測試用例代碼還沒完善，如上述思路有不足之處請(qǐng)批評(píng)指正扩所。
