贪心算法-跳跃游戏二

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

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

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

例如:

 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 条评论
登录 后参与评论

相关文章

来自专栏iKcamp

翻译连载 | 第 9 章:递归(上)-《JavaScript轻量级函数式编程》 |《你不知道的JS》姊妹篇

原文地址:Functional-Light-JS 原文作者:Kyle Simpson-《You-Dont-Know-JS》作者 第 9 章:递归(上) 在下一页...

2039
来自专栏C/C++基础

设计模式 (一)——策略模式(Strategy,行为型)

使用设计模式可以提高代码的可复用性、可扩充性和可维护性。策略模式(Strategy Pattern)属于行为型模式,其做法是将类所需的行为或者算法一个个封装成单...

772
来自专栏Leetcode名企之路

【Leetcode】55. 跳跃游戏

给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1:

823
来自专栏编程

邪恶的编码魔咒,你中招没?

关键时刻,第一时间送达! 自从我观看了Gary Bernhardt所推崇的视频以后,就对某些编程语言的怪异表现着迷了。一些编程语言比其他语言有更多令人感到意外的...

1637
来自专栏java思维导图

经典面试问题: Top K 之 -- 海量数据找出现次数最多或,不重复的

林冠宏 / 指尖下的幽灵 仅列举一些解决方法,事实的解决方案是非常多的。 这些问题都是面临着有如下的考虑: 内存不足以放下所有的数。 机器CPU的核数不够。 ...

3597
来自专栏程序员互动联盟

【编程基础第五讲】java面向对象思想如何理解?

存在的疑惑: 如何理解面向对象的思想? 解决方案: 比如说,我们要用程序来描述一个人。如果是以往的结构化编程,我们可能会这样; 例如用C语言的话,可能会建立一个...

2854
来自专栏专知

关关的刷题日记75 – Leetcode 160. Intersection of Two Linked Lists

关关的刷题日记75 – Leetcode 160. Intersection of Two Linked Lists 题目 ? 思路 思路:题目让求两个单链表...

34413
来自专栏武培轩的专栏

Leetcode#657. Judge Route Circle(判断路线成圈)

初始位置 (0, 0) 处有一个机器人。给出它的一系列动作,判断这个机器人的移动路线是否形成一个圆圈,换言之就是判断它是否会移回到原来的位置。

651
来自专栏数据库

用SQL高性能解决字符串的连续匹配

高性能解决有序集合的连续匹配问题 场景: A集合有8个元素:ali、boy、c、dog、e、f、g、h, B集合有5个元素:boy、c、dog、e、h 问B中...

1889
来自专栏java工会

编写高质量代码的思考

最近在看《代码大全》,可以说是一本软件开发的百科全书,特别厚,但是干货也很多。平时写代码,代码规范是一个最低的要求(很多老代码连最低要求都达不到),为什么要这样...

660

扫码关注云+社区