leetcode https://oj.leetcode.com/problems/jump-game-ii/

1.超时的，效率太低

 1 public class Solution {
 2     public int jump(int[] A) {
 3         int len=A.length;
 4         int d[]=new int[len];
 5         d[0]=0;
 6         
 7         
 8         for(int i=1;i<len;i++)
 9         {
10             d[i]=1;
11             int j;
12             for(j=1;j+i<len&&j<=A[j];j++)
13             {
14                 d[i+j]=Math.max(d[i]+1,d[j+i]);
15             }
16             if(j+i==len) return d[len-1];
17             
18         }
19         
20        return d[len-1];
21         
22     
23         
24         
25         
26         
27     }
28 }

其实根本不用判断的的，只要求出覆盖区域一定是当前最长+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;
    
        
        
        
        
    }
}