贪心算法-跳跃游戏二
发布日期：2021-05-09 04:35:24
浏览次数：22
分类：原创文章
本文共 884 字，大约阅读时间需要 2 分钟。
给定一个非负整数数组，假定你的初始位置为数组第一个下标。
数组中的每个元素代表你在那个位置能够跳跃的最大长度。
你的目标是到达最后一个下标，并且使用最少的跳跃次数。
例如：
A=[2,3,1,1,4]，到达最后一个下标的最少跳跃次数为 2。（先跳跃 1 步，从下标 0 到 1，然后跳跃 3 步，到达最后一个下标。一共两次）
输入格式
第一行输入一个正整数 n(1≤n≤100) ，接下来的一行，输入 n 个整数，表示数组 A。
输出格式
最后输出最少的跳跃次数。
样例输入
53 1 1 1 1
样例输出
2 分析:
通过上面例题分析，类似于贪心算法，每次跳一步后，步数cnt++,然后判断下次跳的最远的距离,直到到达s[n-1]为止,如下图所示:
代码如下:
#include<stdio.h> int n,s[10000]={0},ct=0; int bfs(int i) { int k,j=0,l,max=0; if(i>=n-1) return 0; //找到便退出 k=s[i];ct++; if(i+k>=n-1) return 0; //找到便退出 for(l=i+1;l<=i+k;l++) //for()找到下次能跳到最远的距离 { if(max<=l+s[l]) //更新数据 { j=l;max=l+s[l]; } } bfs(j); //跳到最远的数组里 } int main() { int i; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&s[i]); } bfs(0); printf("%d",ct); //打印步数 return 0; }
下节便来讲动态规划,链接:
发表评论
最新留言
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 465970535 位访客
访问时间: 2025-05-17 01:12:28
访问IP: 18.222.71.250
Copyright © 2020 - 2025 css8.cn 京ICP备2021015314号-1
手机版