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);
}
}
}
