LeetCode--跳跃游戏II(动态规划 贪心算法 回溯法)

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]

输出: 2

解释: 跳到最后一个位置的最小跳跃数是 2。

     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

主函数

public static void main(String[] args) {
    System.out.println("请输入一个数组");
    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine().trim();
    String[] strings = str.substring(1,str.length()-1).split("\\,");
    int[] nums = new int[strings.length];
    for (int i =0;i<strings.length;i++){
        nums[i] = Integer.parseInt(strings[i]);
    }
    System.out.println(jump(nums));
}

思路1  贪心

贪心算法的本质是在动态规划的基础上舍弃一些不可能的情况，类似于回溯算法的剪枝过程。

每一次都是下一步的贪心。下一步贪心最远的就选择哪个

其实重点不在于判断当前位置跳几步，而是要记录在当前位置可以到达的范围内，下一跳可以到达的最远位置，如下面代码中的里层for循环，就记录了当前位置可以到达的范围内，下一跳可以到达的最远位置，而并不关心从当前位置跳多少步。

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int reach = 0;//当前所能到达的最远坐标
        int last = 0;//上一跳可达最远坐标
        int count = 0;//跳跃次数
        for (int i = 0; i < nums.length; i++) {
            if (i > reach) {
                return -1;
            }
            if (i > last) {
                count++;
                last = reach;
            }
            if (i + nums[i] > reach) {
                reach = i + nums[i];
            }
        }
        return count;
    }
}

思路2 动态规划

定义状态：dp[i] 表示到达 i 位置的最小跳数

起始装填：dp[0]=0 到达下标0的最小跳数是0

终止状态：dp[nums.length-1] 即到达最后一个位置的最小跳数

决策：选择 i 之前的能跳到 i 的所有位置j 中， dp[j] 值最小的位置 j 作为上一步要跳到 i 的位置

费用表示：dp[i]=dp[j]+1 ,从 j 跳到 i ,步数加1

无后效性：收益1 是个常数，不随状态改变

class Solution {
    public int jump(int[] nums) {
        int[] dp = new int[nums.length];//dp[i] 为到达 i 位置的最小跳数
        dp[0] = 0;//到达下标0的最小跳数是0
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (i - j <= nums[j]) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[nums.length - 1];
    }
}

方法二

状态定义：f(x, y)--------表示从索引x，走到索引y的最短步数
状态转移：

（1）如果nums[x] + x >= y，说明一步就可以从索引x走到索引y，f(x, y) = 1。

（2）如果nums[x] + x < y，f(x, y) = 1 + min{f(x + 1,y), f(x + 2, y), ... , f(x + nums[x], y)}。

时间复杂度和空间复杂度都是O(n ^ 2)级别的。

JAVA代码：

public class Solution {
 
	//dynamic programming
	public int jump(int[] nums) {
        int n = nums.length;
        if(n == 1) {
        	return 0;
        }
        int[][] steps = new int[n][n];
        for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				steps[i][j] = n - 1;
			}
		}
        for (int i = 0; i < n; i++) {
			steps[i][i] = 0;
		}
        for (int i = 0; i >= 1 - n; i--) {
			for (int j = 0; j < n + i; j++) {
				if(nums[j] + j >= j - i) {
					steps[j][j - i] = 1;
				}else {
					for (int k = 1; k <= nums[j]; k++) {
						steps[j][j - i] = Math.min(steps[j][j - i], 1 + steps[j + k][j - i]);
					}
				}
			}
		}
        return steps[0][n - 1];
    }

思路3：回溯法（在LeetCode中提交会超时）

回溯法的思想很简单，寻找到所有能到达数组的最后一个位置的可能路径
，计算其最短值即可。由于是穷举，其时间复杂度是很高的，达到了
O(nums[0] + nums[1] + nums[2] + ... + nums[n - 1])级别，其中n为nums数组的长度。
而空间复杂度则是递归深度，是O(n)级别的。

JAVA代码：

//backtracking
public class Solution {
	
	int steps;
 
	public int jump(int[] nums) {
        int n = nums.length;
        steps = n - 1;
        
        jump(nums, 0, 0);
        
        return steps;
    }
	
	/*
	 * Now I'm in the indexth position of nums, I have take tempSteps steps
	 */
	private void jump(int[] nums, int index, int tempSteps) {
		if(index >= nums.length - 1) {
			if(index == nums.length - 1) {
				steps = Math.min(steps, tempSteps);
			}
			return;
		}
		for (int i = 1; i <= nums[index]; i++) {
			jump(nums, index + i, tempSteps + 1);
		}
	}
}