贪心算法-跳跃游戏二

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

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

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

例如:

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

相关文章

来自专栏烙馅饼喽的技术分享

用ECMAScript4 ( ActionScript3) 实现Unity的热更新 -- 操作符重载和隐式类型转换

C#中,某些类型会定义隐式类型转换和操作符重载。Unity中,有些对象也定义了隐式类型转换和操作符重载。典型情况有:UnityEngine.Object。Uni...

2787
来自专栏King_3的技术专栏

leetcode-79-单词搜索(用dfs解决)

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

2191
来自专栏Golang语言社区

Go语言 -浮点数

Go提供了两种size的浮点数,float32和float64。它们的算术规范是由IEEE754国际标准定义,现代CPU都实现了这个规范。 浮点数能够表示的范...

3114
来自专栏desperate633

LintCode 数字三角形题目分析1 (常规的动态规划解法)分析2 (如果你只用额外空间复杂度O(n)的条件)

给定一个数字三角形,找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。 ** 注意事项 如果你只用额外空间复杂度O(n)的条件下完成可以获...

772
来自专栏编程之旅

堆排序算法

啊噢,又开始写算法学习的笔记了。最近在准备面试的过程中又把这些常见的排序算法拿出来复习复习,既然这篇写到了堆排序,那么就代表堆排序算法的概念被我忘的差不多了,写...

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

洛谷P3327 [SDOI2015]约数个数和(莫比乌斯反演)

题目描述 设d(x)为x的约数个数,给定N、M,求 \sum^N_{i=1}\sum^M_{j=1}d(ij)∑i=1N​∑j=1M​d(ij) 输入输出格式 ...

2644
来自专栏kalifaの日々

POJ2431-最优队列(最小堆)解法

这道题有一个坑,就是给出的加油站到终点的距离不一定是降序排列好了的。 所以得到input之后要先对数据进行排序。我直接用了#include<algorithm>...

3417
来自专栏mathor

2017百度之星初赛(A):小C的倍数问题

 假设P进制下有个数(abc)~P~,若这个数满足:(abc)~P~ % B == 0,则以下两个等式一定成立:

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

P1888 三角函数

题目描述 输入一组勾股数a,b,c(a≠b≠c),用分数格式输出其较小锐角的正弦值。(要求约分。) 输入输出格式 输入格式: 一行,包含三个数,即勾股数...

2807
来自专栏GIS讲堂

Geotools中实现NC转等值面

前面的文章有实现IDW插值并生成等值面的,本文在前文基础上实现气象NC数据生成等值面。

1454

扫码关注云+社区