首页 > 代码库 > 计蒜客-题库-跳跃游戏2
计蒜客-题库-跳跃游戏2
题目
给定一个非负整数数组,假定你的初始位置为数组第一个下标。
数组中的每个元素代表你在那个位置能够跳跃的最大长度。
你的目标是到达最后一个下标,并且使用最少的跳跃次数。
例如:
A=[2,3,1,1,4],到达最后一个下标的最少跳跃次数为 2。(先跳跃 1步,从下标 0到 1,然后跳跃 3 步,到达最后一个下标。一共两次)
输入格式
第一行输入一个正整数 n(1≤n≤100),接下来的一行,输入 n个整数,表示数组 A。
输出格式
最后输出最少的跳跃次数。
样例输入
5 3 1 1 1 1
样例输出
2
代码
#include<iostream> using namespace std; int n; int s[100]; int t[100] = { 0 }; int dfs(int src, int des){ //只有一个数字时,不需要跳 if (src =http://www.mamicode.com/= 0){ return 0; } //如果des小于0,说明当前位置从起点到不了 if (des < 0){ return -1; } /*从当前位置往前查找从起点到本点所有路径中的直接邻点,那么当前点的跳跃数就是这些点得跳跃数 加1,然后选取最小的。 */ for (int i = des; i >= 0; --i){ if (s[i] >= src - i){//可能邻点 if (t[i] == 0){ t[i] = dfs(i, i - 1); } if (t[src] == 0 || t[src] > t[i] + 1){ t[src] = t[i] + 1; } } } return t[src]; } int main(){ cin >> n; for (int i = 0; i < n; ++i){ cin >> s[i]; } cout << dfs(n - 1, n - 2) << endl; return 0; }
计蒜客-题库-跳跃游戏2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。