题解 | #几步可以从头跳到尾#

本题通常解法是广度优先遍历，算法的复杂度是O(n2)
动态规划巧妙解决方法：
猜测状态f[n-1].....因为会有很多种情况可以一步跳到n-1,f[i]表示到达第i个位置所需要的最少步数
f[n-1]=min(f[n-k],f[n-3],f[n-2])+1
对于f[n-k]<=f[n-k-1]<=f[n-3]<=f[n-2] 因此当我们要求某一个f[i]的时候，我们需要找到最早能够经过一步到达i点的j点。
f[i]=f[j]+1
对于j点的选择，应该是贪心算法---使得j离得i最远
``` import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少需要跳跃几次能跳到末尾
     * @param n int整型 数组A的长度
     * @param A int整型一维数组 数组A
     * @return int整型
     */
    public int Jump (int n, int[] A) {
        // write code here
        int []f=new int[n];
        for(int i=1,j=0;i<n;i++){
            while(j+A[j]<i)j++;
            f[i]=f[j]+1;
        }return f[n-1];
    }
}
```