题解 | #几步可以从头跳到尾#
几步可以从头跳到尾
http://www.nowcoder.com/practice/de62bcee9f9a4881ac80cce6da42b135
本题通常解法是广度优先遍历，算法的复杂度是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]; } } ```
哔哩哔哩公司福利 357人发布
查看7道真题和解析
腾讯一面1793人在聊