原题链接:https://code.mi.com/problem/list/view?id=119
描述
米兔爸爸为了让小米兔好好锻炼身体，便给小米兔设置了一个挑战——跳格子。
要吃到自己心爱的胡萝卜，小米兔需要跳过面前一些格子。现有
NN
N 个格子，每个格子内都写上了一个非负数，表示当前最多可以往前跳多少格，胡萝卜就放在最后一个格子上。米兔开始站在第 1 个格子，试判断米兔能不能跳到最后一个格子吃到胡萝卜呢？
输入
输入为
NN
N 个数字 (
N<10N \lt 10
N<10)，用空格隔开，第
ii
i 个数字
sis_i
s
i
?
(
0≤si<10 0 \le s_i \lt 10
0≤s
i
?
<10) 表示米兔站在第
ii
i 个格子上时，最多能往前跳的格数。
输出
若米兔能跳到最后一个格子上吃到胡萝卜，输出 “true“，否则输出 “false“
输入样例
2 0 1 0 0 3 4
复制样例
输出样例
false
贪心:
#include <iostream>
const int N=100;
using namespace std;
int a[N];
int mp[N];
int cnt=0;
int main()
{
int g;
char c;
while(cin>>g){
a[++cnt]=g;
c=cin.get();
if(c!=' ') break;
}
mp[1]=1;
for(int i=1;i<=cnt;i++){
if(mp[i]==1)
for(int j=1;j<=a[i];j++){
if(i+j<=cnt) mp[i+j]=1;
}
}
//cout << "Hello world!" << endl;
return 0;
}DFS:
#include <iostream>
const int N=100;
using namespace std;
int a[N];
int mp[N];
int cnt=0;
bool dfs(int now){
if(now==cnt) return true;
for(int i=1;i<=a[now];i++){
if(i+now<=cnt&&dfs(i+now)) return true;
}
return false;
}
int main()
{
int g;
char c;
while(cin>>g){
a[++cnt]=g;
c=cin.get();
if(c!=' ') break;
}
if(dfs(1)) cout<<"true"<<endl;
else cout<<"false"<<endl;
//cout << "Hello world!" << endl;
return 0;
}