使用動態規劃求解問題，最重要的就是確定動態規劃三要素： （1）問題的階段 （2）每個階段的狀態 （3）從前一個階段轉化到后一個階段之間的遞推關系。 遞推關系必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動態規劃往往可以用遞歸程序來實現，不過因為遞推可以充分利用前面保存的子問題的解來減少重復計算，所以對于大規模問題來說，有遞歸不可比擬的優勢，這也是動態規劃算法的核心之處。 確定了動態規劃的這三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表是一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關系，從1行1列開始，以行或者列優先的順序，依次填寫表格，最后根據整個表格的數據通過簡單的取舍或者運算求得問題的最優解。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

給定一個非負整數數組，假定你的初始位置為數組第一個下標。

數組中的每個元素代表你在那個位置能夠跳躍的最大長度。

你的目標是到達最后一個下標，并且使用最少的跳躍次數。

例如：

A=[2,3,1,1,4]，到達最后一個下標的最少跳躍次數為 22。（先跳躍 11 步，從下標 00 到 11，然后跳躍 33 步，到達最后一個下標。一共兩次）

輸入格式

第一行輸入一個正整數 n(1 /le n /le 100)n(1≤n≤100) ，接下來的一行，輸入 nn 個整數，表示數組 AA。

輸出格式

最后輸出最少的跳躍次數。

樣例輸入

5 3 1 1 1 1 樣例輸出

2

分析題目： 針對例子 2 3 1 1 4 問題的階段： 走到第幾格，表示一個階段，這里共有5個階段 用d[i]表示各個階段，首先第一階段為d[0] = 0(0表示不用走，0步); 每個階段的狀態： d[0] = 0 d[1] = d[0]+1（條件為2>1-0;）； d[2] = min{d[0]+1,d[1]+1}; d[3] = min{d[1]+1,d[2]+1}; ………. 從前一個階段轉化到后一個階段之間的遞推關系： d[i] = min{d[j]+1};為最后的狀態轉移方程式