【算法】袋鼠过河，动态规划问题（C++源码）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法】袋鼠过河，动态规划问题（C++源码），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1153字，纯文字阅读大概需要2分钟。

内容图文

问题描述

一只袋鼠要从河这边跳到河对岸，河很宽，但是河中间打了很多桩子，每隔一米就有一个，每个桩子上有一个弹簧，袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同，用一个数字代表它的力量，如果弹簧的力量为5，就表示袋鼠下一跳最多能够跳5米，如果为0，就表示陷阱去无法继续跳跃。河流一共n米宽，袋鼠初始在第一个弹簧上面，若跳到最后一个弹簧就算过河了，给定每个弹簧的力量，求袋鼠最少需要多少跳能够到达对岸。如果无法到达，输出-1。

输入描述

输入分两行，第1行是数组长度，第2行是每一项的值，用空格分开。

输出描述

输出最少的跳数，若无法到达输出-1。

输入样例

5 2 0 1 1 1

输出样例

4

步骤描述

temp表示临时存放当前所处的位置，now表示当前位置，step表示步数。比较当前跳的步数加上落地点的步数和临时步数的大小，输出较远的那个，若i循环到跳到的桩子上，则将步数++，临时步数记到当前位置上。当i循环玩判断，当前位置是否大于河的宽度，若大于则输出步数，若小于则输出-1.

运行结果截图

源代码（C++）

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int temp=0,step=0,now=0;
    for(int i=0;i<n;i++)
    {
        temp=max(temp,now+a[i]);
        if(now==i)
        {
            step++;
            now=temp;
        }
    }
    if(now>=n)
    {
        cout<<step<<endl;
    }
    else
    {
        cout<<"-1"<<endl;
    }
    return 0;
}

内容总结

以上是互联网集市为您收集整理的【算法】袋鼠过河，动态规划问题（C++源码）全部内容，希望文章能够帮你解决【算法】袋鼠过河，动态规划问题（C++源码）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---