【DP+贪心】跳跃游戏

一、题目

题目来源：LeetCode

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

示例如下：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
1
2
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++代码

思路一代码：

#include
using namespace std;

#define maxn 10010
int 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";
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

思路二代码：

#include
using namespace std;

#define maxn 10010
bool 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";
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45