跳跃游戏二

跳跃游戏二

题目:

给定一个非负整数数组,假定你的初始位置为数组第一个下标。

数组中的每个元素代表你在那个位置能够跳跃的最大长度。

你的目标是到达最后一个下标,并且使用最少的跳跃次数。

例如:

A = [2,3,1,1,4], 到达最后一个下标的最少跳跃次数为2.(先跳跃1步,从下标0到1,然后跳跃3步,到达最后一个下标。一共两次)

格式:

第一行输入一个正整数n,接下来的一行,输入数组A[n]。

最后输出最少的跳跃次数。

样例输入

5
3 1 1 1 1

样例输出

2

思路:

设当前所在的下标为cur,已经走的次数为count,则走到终点的最少步数为solve(cur,count)

用B[cur]保存以cur为起点,走到终点的最少步数。

则有:

slove(cur,count)=B[cur]+count

B[cur]=min{slove(cur+1,1),solve(cur+2,1)…..solve(cur+i,1)}(i<=A[cur])

所以最终的状态转移方程为:

slove(cur,count)=min{slove(cur+1,1),solve(cur+2,1)…..solve(cur+i,1)}+count (i<=A[cur])

代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100000+10;
int A[maxn];
int B[maxn];
int N;
int solve(int cur,int count){
	if(B[cur]>0) return B[cur]+count;
	if(cur>=N-1) return (B[cur]=0)+count;
	int t=0,min=N+1;
	for(int i=1;i<=A[cur];i++){
		t=solve(cur+i,1);
		if(t<min) min=t;
	}
	return (B[cur]=min)+count; 
}
int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++)  scanf("%d",&A[i]);
	memset(B,-1,sizeof(B));
	printf("%d\n",solve(0,0));	
	return 0;
} 
2016年5月14日 | 归档于 Uncategorized
标签:
本文的评论功能被关闭了.