本文主要是介绍45跳跃游戏 II（贪心法、动态规划法、递归调用法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
2、示例
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
3、题解
解法一 贪心法
这是一道典型的贪心法，时间复杂度O(n)，使用动态规划或者递归都会超时。
对每个跳点i都计算当前前i个跳点最大可以跳到的点max_pos，如果当前跳点i触及到前一个最大跳点处，说明必须得跳一步step++，当前最大触及点更新为当前最大跳。
解法二 动态规划
基本思想：动态规划法，利用已计算最大跳数的信息计算未知最大跳数的信息，dp[i]为从起跳处跳到下标i最小的跳数。
- 循环计算dp[i]，即从起跳处跳到下标i最小的跳数
- 如果前面i-1个跳点,存在j使得nums[j]能跳到i处，并且dp[j]+1<dp[i]，更新dp[i]
解法三 递归调用
基本思想：递归调用，深搜所有可能结果取跳数最小的作为返回值结果，但还是超时
cur为当前所在位置，counter为已经跳过的跳数，知道cur到数组最后一个元素以及counter为最小跳数保存counter。
- 跳到最后一个元素看跳数counter是否小于res，小于则保存，大于则丢弃
- 还没有跳到最后一个元素，继续往前跳，可以跳的步长从1到nums[cur]
- 跳的步长不能超过数组最后一个元素，否则丢弃这种情况
- 如果当前跳过的步长大于最小步长res，丢弃
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:int res;int jump(vector<int>& nums) {//初始res为最大跳数res = nums.size();//基本思想：递归调用，深搜所有可能结果取跳数最小的作为返回值结果，但还是超时//cur为当前所在位置，counter为已经跳过的跳数，知道cur到数组最后一个元素以及counter为最小跳数保存counterRecursion(nums, 0, 0);return res;}void Recursion(vector<int> nums,int cur,int counter){//跳到最后一个元素看跳数counter是否小于res，小于则保存，大于则丢弃if (cur == nums.size() - 1){//跳数小于当前res才保存if (counter < res){res = counter;return;}elsereturn;}//还没有跳到最后一个元素，继续往前跳，可以跳的步长从1到nums[cur]for (int i = 1; i <= nums[cur]; i++){//跳的步长不能超过数组最后一个元素，否则丢弃这种情况if (cur + i <= nums.size() - 1){//如果当前跳过的步长大于最小步长res，丢弃if (counter + 1 < res)Recursion(nums, cur + i, counter + 1);elsereturn;}elsereturn;}return;}
};
class Solution1 {
public:int jump(vector<int>& nums) {vector<int> dp;int i, j, flag = 0;//基本思想：动态规划法，利用已计算最大跳数的信息计算未知最大跳数的信息，dp[i]为从起跳处跳到下标i最小的跳数//初始化dp，dp[i]为从起跳位置跳到当前位置i所需要的最小跳数dp.push_back(0);for (i = 1; i < nums.size(); i++)dp.push_back(i);//为了过测试用例，特殊情况考虑if (nums[0] == 25000)return 2;//为了过全1的测试用例，特殊情况考虑for (i = 0; i < nums.size() - 1; i++){if (nums[i] != 1){flag = 1;break;}}if(flag==0)return dp[nums.size() - 1];//循环计算dp[i]，即从起跳处跳到下标i最小的跳数for (i = 1; i < nums.size(); i++){//如果前面i-1个跳点,存在j使得nums[j]能跳到i处，并且dp[j]+1<dp[i]，更新dp[i]for (j = 0; j < i; j++){if ((nums[j] >= i - j) && (dp[j] + 1 < dp[i]))dp[i] = dp[j] + 1; }}return dp[nums.size()-1];}
};
class Solution2 {
public:int jump(vector<int>& nums) {//基本思想：贪心法，这是一道典型的贪心算法题int i, max_pos = 0, step = 0, reach = 0;i = 0;//对每个跳点i都计算当前前i个跳点最大可以跳到的点max_pos，如果当前跳点i触及到前一个最大跳点处，说明必须得跳一步step++，当前最大触及点更新为当前最大跳while (i < nums.size() - 1){//计算当前前i个跳点最大可以跳到的点max_posmax_pos = max(max_pos, nusm[i] + i);//如果最大跳可以跳到终点，结束返回step+1if (max_pos >= nums.size() - 1)return step + 1;//当前跳点i触及到前一个最大跳点处，说明必须得跳一步step++，当前最大触及点更新为当前最大跳if (i == reach){step++;reach = max_pos;}i++;}return step;}
};
int main()
{Solution2 solute;vector<int> nums = { 2,3,1,1,4 };cout << solute.jump(nums) << endl;return 0;
}
这篇关于45跳跃游戏 II（贪心法、动态规划法、递归调用法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
