本文主要是介绍头歌-EduCoder:袋鼠过河问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

头歌-EduCoder:袋鼠过河问题

• 任务描述
• 题目描述
• 编程要求
• 测试说明
• 代码实现

任务描述

本关任务：编写一个袋鼠过河问题的小程序。

题目描述

一只袋鼠要从河这边跳到河对岸，河很宽，但是河中间打了很多桩，每隔一米就有一个，每个桩上面有一个弹簧，袋鼠跳到弹簧上就可以跳得更远。每个弹簧力量不同，用一个数字代表它的力量，如果弹簧力量为5，就表示袋鼠下一跳最多能够跳5米；如果为0，就表示会陷进去无法继续跳跃。河流一共n米宽，袋鼠初始在第一个弹簧上面，若跳到最后一个弹簧就算过河了。给定每个弹簧的力量，求袋鼠最少需要多少跳能够到达对岸。如果无法到达，输出-1。

编程要求

根据提示，在右侧编辑器 Begin-End 补充代码，完成袋鼠过河问题

测试说明

平台会对你编写的代码进行测试：

输入描述：输入分两行，第1行是数组长度n(1<=n<=10000)，第2行是每一项的值，用空格分隔。
输出描述：输出最少的跳数，若无法到达输出-1。

测试输入：

5
2 0 1 1 1

预期输出：
4

代码实现

#include <iostream>

/********* Begin *********/
#include<stdlib.h>
#include<stdio.h>

int main(){
    
	int m;
	scanf("%d",&m);
	int *a=(int*)malloc(sizeof(int)*m);
	int *dp=(int*)malloc(sizeof(int)*m);
	for(int i=0;i<m;i++){
    
	scanf("%d",&a[i]);
	}
	for(int i=0;i<m;i++){
    
		dp[i]=0;
	      for(int j=0;j<i;j++){
    
	          if(dp[j]!=-1&&j+a[j]>=i){
    
	             int min=dp[j]+1;
	             if(dp[i]==0||dp[i]==-1){
    
	                   dp[i]=min;
	             }
	             else{
    
	                  dp[i]=dp[i]<min?dp[i]:min;
	
	             }
	          }
	      }
	     if(dp[i]==0&&i!=0){
    
	            dp[i]=-1;
	   }
	
	}
	printf("%d",dp[m-1]);
	return 0;
}
/********* End *********/

这篇关于头歌-EduCoder:袋鼠过河问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！