贪心算法-跳跃游戏二

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

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

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

例如:

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

输入格式

第一行输入一个正整数 n(1≤n≤100) ,接下来的一行,输入 n 个整数,表示数组 A。

输出格式

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

样例输入

5
3 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;
 } 

 下节便来讲动态规划,链接:http://www.cnblogs.com/lifexy/p/7550159.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏owent

C++ 新特性学习(六) — 新的字符串编码和伪随机数

使用u””为能至少储存UTF-16的16位元编码,对应’\u’表示16位元的字符。

571
来自专栏Golang语言社区

深入解析快速排序算法的原理及其Go语言版实现

快速排序是一种基于分治技术的重要排序算法。不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分。具体来说,它对给定数组中的元素...

3165
来自专栏数据结构与算法

P1062 数列

题目描述 给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是: 1,3,4,9,...

2657
来自专栏数据结构与算法

21:角谷猜想

21:角谷猜想 总时间限制: 1000ms 内存限制: 65536kB描述 所谓角谷猜想,是指对于任意一个正整数,如果是奇数,则乘3加1,如果是偶数,则除以2...

3547
来自专栏赵俊的Java专栏

落单的数

1652
来自专栏noteless

[十]基础数据类型之Unicode编码简介

(American Standard Code for Information Interchange,美国信息交换标准代码)

662
来自专栏开发与安全

算法:队列与广度优先搜索(迷宫问题)

队列也是一组元素的集合,也提供两种基本操作:Enqueue(入队)将元素添加到队尾,Dequeue(出队)从队头取出元素并返回。就像排队买票一样,先来先服务,先...

2427
来自专栏猿人谷

memcpy和memmove的区别

memcpy()和memmove()都是C语言中的库函数,在头文件string.h中,其原型分别如下: void *memcpy(void *dst, con...

1965
来自专栏有趣的Python

算法与数据结构(二):排序篇-O(n^2)算法:选择 & 插入算法优化排序基础

排序基础 O(n^2)的算法虽然简单,但也实用!让我们从最简单的基础排序算法开始,打开我们的算法大门! 排序算法 O(n^2)的排序算法 最优的时间复杂度为O...

3014
来自专栏ml

字符中的小知识(“123”的十进制是多少)

        在数据库,录入数据的时候,遇到一个小问题。当设置变量的类型为 Bit 时,你写进去的数据为:“123”时, 会显示一个这样的数值:3224115...

40710

扫码关注云+社区