1.超时的，效率太低
public class Solution {
public int jump(int[] A) {
int len=A.length;
int d[]=new int[len];
d[0]=0;
for(int i=1;i<len;i++)
{
d[i]=1;
int j;
for(j=1;j+i<len&&j<=A[j];j++)
{
d[i+j]=Math.max(d[i]+1,d[j+i]);
}
if(j+i==len) return d[len-1];
}
return d[len-1];
}
}
其实根本不用判断的的，只要求出覆盖区域一定是当前最长+1；
public class Solution {
public int jump(int[] A) {
int len=A.length;
int step=0;
int last=0;
int maxpost=0;
for(int i=0;i<len;i++)
{
if(i>last)
{
step++;
last=maxpost;
}
maxpost=Math.max(i+A[i],maxpost);
}
return step;
}
}
AC代码
public class Solution {
public int jump(int[] A) {
int len=A.length; int step=0;//记录当前的步骤
int last=0; //当前步骤达到的最大值
int maxpost=0;//当前能扩张的最大范围 ，很像bfs啊，一层一层的，bfs就是求最小距离的啊 for(int i=0;i<len;i++)
{
if(i>last)
{
step++;
last=maxpost; } maxpost=Math.max(i+A[i],maxpost); } return step; }
}