每日一道算法题之跳跃游戏

  • 一、题目
  • 二、思路
  • 三、C++代码

一、题目

题目来源：LeetCode

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例如下：

输入：nums = [2,3,1,1,4]输出：true解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

 

二、思路

  这个题目有DP和贪心两种解法，由于采用贪心解法更方便所以先讲贪心的解法。
 思路一：贪心： 这个问题的实质在于每一个位置的跳跃距离最终是否能覆盖到终点，每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
  贪心算法局部最优解： 每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
 时间复杂度: O(n)

  思路二：动态规划

  按照动态规划五部曲进行分析：

  1. 确定dp数组的含义
    dp[i]:为bool类型，表示的是能否从位置i到达位置n-1。

  2. 确定递推公式
    这里我们还用一个变量furtherjump来表示当前位置能够到达的最远距离。我们从数组的倒数第二个位置开始向左遍历数组，更新 dp 数组的值。对于每个位置 i，我们计算从当前位置能够到达的最远位置 furthestJump，然后检查从 i+1 到 furthestJump 之间的位置是否有能够跳到最后一个位置的情况，如果有，则将 dp[i] 设为 true。最终返回 dp[0] 的结果。
    确定遍历顺序

  3. dp数组初始化
    dp[n-1]=true,因为最后一个位置肯定可以跳到本身位置上。然后其它dp[i]初始化为false。

  4. 确定遍历顺序
    从后往前进行遍历

三、C++代码

思路一代码：

#includeusing namespace std;#define maxn 10010int nums[maxn];bool jump(int nums[],int n){ int cover=0;if(n==1){return true; } for(int i=0;i<=cover;i++){cover=max(i+nums[i],cover);if(cover>=n-1){return true;} }return false;}int main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>nums[i];}if(jump(nums,n)){cout<<"true";}else{cout<<"false";}}

思路二代码：

#includeusing namespace std;#define maxn 10010bool dp[maxn];int nums[maxn];bool jump(int nums[],int n){//dp数组初始化for(int i=0;i<n;i++){dp[i]=false;} dp[n-1]=true; //最后一个位置可以跳到自己//确定递推公式for(int i=n-2;i>=0;--i){int furtherjump=min(i+nums[i],n-1); //当前位置能够到达的最远位置 for(int j=i+1;j<=furtherjump;j++){if(dp[j]){ //如果从j位置可以跳到最后一个位置 dp[i]=true;//则从i位置也可以跳到最后一个位置 break;//不需要再检查后面的位置 }} }return dp[0]; }int main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>nums[i];}if(jump(nums,n)){cout<<"true";}else{cout<<"false";}}