文档章节

袋鼠过河python

hc321
 hc321
发布于 2018/04/06 20:54
字数 398
阅读 66
收藏 0

一只袋鼠要从河这边跳到河对岸,河很宽,但是河中间打了很多桩子,每隔一米就有一个,每个桩子上都有一个弹簧, 袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同,用一个数字代表它的力量,如果弹簧力量为5,就代表袋鼠下一跳最多能够跳5米, 如果为0,就会陷进去无法继续跳跃。河流一共N米宽,袋鼠初始位置就在第一个弹簧上面,要跳到最后一个弹簧之后就算过河了, 给定每个弹簧的力量,求袋鼠最少需要多少跳能够到达对岸。如果无法到达输出-1 输入描述: 输入分两行,第一行是数组长度N (1 ≤ N ≤ 10000),第二行是每一项的值,用空格分隔。 输出描述: 输出最少的跳数,无法到达输出-1 示例1 输入 5 2 0 1 1 1 输出 4

#递归方法
lens=int(input())
lists=list(map(int,input().split()))
ind_get={}
for i in range(1,lens+1):
    ind_get[i]=list(range(i+1,i+lists[i-1]+1))
def get_min(ind_get,ind):
    get_list=[]
    if ind==1:
        return 1
    for k, v in ind_get.items():
        if k < ind and ind in v:
            get_list.append(get_min(ind_get, k))
    min_num=min(get_list)
    return min_num+1
res=get_min(ind_get,lens)
print(res)
#动态规划
lens=int(input())
lists=list(map(int,input().split()))
dp=[i for i in range(lens+1)]
for i in range(lens+1):
    if i ==0:
        continue
    flag=False
    for j in range(i):
        if j+lists[j] >= i:
            dp[i]=min(dp[i],dp[j]+1)
            flag=True
    if flag==False:
        break
if flag==True:
    print(dp[lens])
else:
    print("-1")

© 著作权归作者所有

共有 人打赏支持
上一篇: 分苹果
下一篇: 1. Two Sum
hc321
粉丝 2
博文 80
码字总数 43836
作品 0
海淀
程序员
私信 提问
8月编程语言排行榜:Objective-C迈进TOP20

【开源中国社区讯】Tiobe今日公布了2009年8月的编程语言排行榜,Object-C继上个月排名第21的良好上升势头,由市场占有率0.509%(上月)上升到这个月的0.612%,排名为19。 前10名的变化几无变...

小卒过河
2009/08/02
1K
5
12月6日云栖精选夜读 | 三张图读懂机器学习 :基本概念、五大流派与九种常见算法

机器学习正在进步,我们似乎正在不断接近我们心中的人工智能目标。语音识别、图像检测、机器翻译、风格迁移等技术已经在我们的实际生活中开始得到了应用,但机器学习的发展仍还在继续,甚至被...

yq传送门
2018/12/06
0
0
开源工具收集与评论平台VSMatrix.info

这个时代的程序员是幸福的,因为有无数优秀的免费的工具、无数的优秀的开源的软件包为我们的工作提供便利; 这个时代的程序员也是痛苦的,因为选择太多,有时候让人无所适从。 网上常见的热门...

hyperkang
2015/05/26
1
0
想找一个C软件方向的工作,转行真心不容易

大家好啊,先介绍下自己哈 。 2011届江苏大学材料类毕业生,但酷爱软件。毕业后在武钢股份公司上班,工作期间开始学习了解作为一个 合格C/C++程序员所需要的知识。去年年底辞职后,来北京找工...

Hyacinthus_M
2013/03/12
2.1K
20
2016.1.6~2017.7.7,袋鼠云一岁半啦

2017上半年真是转瞬即逝,昨天7月6号,也是袋鼠云成立一年半的日子。 创始人之一,袋鼠云CTO江枫(袋鼠江湖人称“袋鼠长老2号”)也不由得在朋友圈发起了感慨: 宁海元 花名江枫 袋鼠云CTO 依...

袋鼠云
2017/07/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Pages Manager——可本地管理Pages服务内容,一键生成漂亮的文档界面。

Pages Manager Git地址 可本地管理Pages服务内容,一键生成漂亮的文档界面。在线预览 简单、轻便,无需安装数据库。 框架:spring-boot 数据库:sqlite 原理 本地维护一组markdown文档 将mar...

tanghc
14分钟前
0
0
基础目标检测算法介绍:CNN、RCNN、Fast RCNN和Faster RCNN

每次丢了东西,我们都希望有一种方法能快速定位出失物。现在,目标检测算法或许能做到。目标检测的用途遍布多个行业,从安防监控,到智慧城市中的实时交通监测。简单来说,这些技术背后都是强...

AI女神
15分钟前
0
0
哪有什么互联网寒冬?只是你穿的少而已!

声明:本文由终端研发部原创发布,未经允许,不得转载 前言 最近一段时间,大家都在说一些大公司纷纷裁员, 优化公司内部的组织架构。面对如此的寒冬变化,很多人在迷茫,在焦虑,在担忧自己...

终端研发部
20分钟前
0
0
nginx: [error] open() "/var/run/nginx.pid" failed (2: No such file or directory)

Nginx 启动时报错:nginx: [error] open() "/var/run/nginx.pid" failed (2: No such file or directory) 原因:系统重启 /var/run/ 目录下文件会清空。 方法一: # sudo nginx -c /etc/ngi......

驛路梨花醉美
22分钟前
1
0
TiDB 源码阅读系列文章(二十四)TiDB Binlog 源码解析

作者:姚维 TiDB Binlog Overview 这篇文章不是讲 TiDB Binlog 组件的源码,而是讲 TiDB 在执行 DML/DDL 语句过程中,如何将 Binlog 数据 发送给 TiDB Binlog 集群的 Pump 组件。目前 TiDB 在...

TiDB
35分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部