本文共 1401 字，大约阅读时间需要 4 分钟。

Leedcode45----跳跃游戏2

方案一:动规+逆向思维

class Solution{
       //逆向思维    public int jump(int[] nums) {
           int f[] = new int[nums.length];        f[nums.length-1] = 0;        for(int i=nums.length-2;i>=0;i--)            AddNew(f,nums,i);        return f[0];    }    //f[i]代表从从索引i到达最后需要的最少步数(dp),f[i]=-1代表其无法到达最后    void AddNew(int f[],int[] nums,int index)    {
           int firstPosi = nums.length-1;        if(index+nums[index]
   
    =index+1;i--)//只看f[index]到达的聊得地方        {
               //该位置不可用            if(f[i]==-1)                continue;           //当f[index]=0时，此时不可以做最小比较，因为做了还是0            //这个时候是初始时候            if(f[index]==0)            {
                       f[index] = f[i]+1;            }            else {
                   f[index]= java.lang.Math.min(f[index],f[i]+1);            }        }        //无法到达则改为-1        if(f[index]==0)            f[index]=-1;    }}
   

2.贪心

基本思路:f[i]表示从0到i所需要的最小1步数;f[i]的排列方式为0 1 1 1 2 2 2 3 3 3 4 4 ...一直到最后一个位置

class Solution{
       public int jump(int[] nums) {
          //表示从f[i]表示从0到i的最小步数,其中f[0]=0        int[] f = new int[nums.length];        //i表示当前段的起点,表示终点        // 比如0为一段,1 1 1又为一段        int i=0,j=0,current=1;        int num = 0;//开始进入字段1的标记        while(j
   
    nums.length-1)                max = nums.length-1;            num++;            i=j+1;            j=max;        }        return  num;    }}
   

转载地址：http://jplzi.baihongyu.com/