每日一题C++版（袋鼠过河）
编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化和锻炼自己的编程能力（最起码不会忘记编程）
特别说明：编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法，所以提供的代码不一定是最优解，但是本文提供的编程代码均为通过测试代码。
袋鼠过河
题目描述
一只袋鼠要从河这边跳到河对岸，河很宽，但是河中间打了很多桩子，每隔一米就有一个，每个桩子上都有一个弹簧，袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同，用一个数字代表它的力量，如果弹簧力量为5，就代表袋鼠下一跳最多能够跳5米，如果为0，就会陷进去无法继续跳跃。河流一共N米宽，袋鼠初始位置就在第一个弹簧上面，要跳到最后一个弹簧之后就算过河了，给定每个弹簧的力量，求袋鼠最少需要多少跳能够到达对岸。如果无法到达输出“-1”
输入描述:
输入分两行，第一行是数组长度N (1 ≤ N ≤10000)，第二行是每一项的值，用空格分隔。
输出描述:
输出最少的跳数，无法到达输出-1
示例
输入
5
2 0 1 1 1
输出
4
解析
本题是一个动态规划的问题，当然也可以用dp[]来实现。小白为大家提供了两种解决方案，不过后一种并没有考虑如何判定不能到达的情况，请小伙伴们可以自己思考一下。好了，首先讲解一下我们的思路。我们从后往前想，当我站在某处的时候，一定希望是最远的弹簧跳过来的，这样我们就判定我们前面的弹簧距离我们的位置和它本身的弹力，寻找到离我们最远的（程序中也就是从前完后的第一个能跳到该位置的弹簧），如果没有找到，就是无法跳过河。放我们找到最远的弹簧之后，便寻找能跳到那个弹簧上的最远的弹簧直到遇到第一个弹簧。
注释掉的是采用dp[]思路去解决的，感兴趣的小伙伴可以尝试一下。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
vector<int> fox;
Solution(){};
int step(int i)
{
for (int j = 0; j < i; j++)
{
if (fox[j]>=(i-j))//从左找最远的能跳到当前位置的号码
{
return j;
}
}
return -1;
}
private:
};
int main()
{
int index;
while (cin>>index)
{
vector<int> fox;
for (int i = 0; i < index; i++)
{
int f;
cin >> f;
fox.push_back(f);
}
int step=0;
int current = fox.size();
Solution solution;
solution.fox = fox;
while (current!=0)
{
current = solution.step(current);
if (current==-1)
{
cout << "-1" << endl;
return 0;
}
step++;
}
cout << step << endl;
}
return 0;
}
//int main()
//{
// int index;
// while (cin >> index)
// {
// vector<int> fox;
// for (int i = 0; i < index; i++)
// {
// int f;
// cin >> f;
// fox.push_back(f);
// }
// vector<int> step(fox.size() + 1, fox.size() + 1);
// step[0] = 0;
// for (int i = 0; i < fox.size(); i++)
// {
// for (int j = 1; j <= fox[i]; j++)
// {
// if (i + j >= step.size())
// {
// break;
// }
// step[i + j] = min(step[i + j], step[i] + 1);
// }
// }
// cout << *(--step.cend()) << endl;
// }
// return 0;
//}运行结果
腾讯云开发者
