链接如下:
这是上一个条约游戏的延伸.看到这题第一个想法是把所有情况列出来,但是这样复杂度明显就高了,所以应该做一下动态规划,将到每一步最快的步数记录下来以防止多次计算.
给定一个非负整数数组，假定你的初始位置为数组第一个下标。数组中的每个元素代表你在那个位置能够跳跃的最大长度。你的目标是到达最后一个下标，并且使用最少的跳跃次数。
例如：
A=[2,3,1,1,4]A = [2,3,1,1,4]A=[2,3,1,1,4]，到达最后一个下标的最少跳跃次数为222。（先跳跃111步，从下标000到111，然后跳跃333步，到达最后一个下标。一共两次）
输入格式
第一行输入一个正整数n(1≤n≤100)n(1 \le n \le 100)n(1≤n≤100)，接下来的一行，输入nnn个整数，表示数组AAA。
输出格式
最后输出最少的跳跃次数。
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
int i,j;
int dp[101];//记录到每一步最快方法
int n,data[101];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&data[i]);
fill(dp,dp+100,101);//因为是最小,所以初始值设为最大.
dp[0]=0;
for(i=0;i<n;i++){
for(j=1;j<=data[i];j++){
if(i+j>n-1) break;
dp[i+j]=min(dp[i+j],dp[i]+1);
}
}
printf("%d",dp[n-1]);
return 0;
}
