文档章节

袋鼠过河python

hc321
 hc321
发布于 04/06 20:54
字数 398
阅读 49
收藏 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
粉丝 1
博文 67
码字总数 32581
作品 0
海淀
程序员
私信 提问
袋鼠,自动驾驶也无法攻克的生物,仿真或有希望?

     雷锋网新智驾按:无人驾驶已经成为全球的潮流,很多国家都在促成无人驾驶汽车上路。澳洲也在不遗余力地推进,但澳洲是一个很特殊的国家,那里有很多的袋鼠。没错,就是这个可爱的弹...

深度学习
05/05
0
0
智能运维案例系列 | 新网银行 X 袋鼠云:银行核心业务系统日志监控平台建设实践

在聊今天的案例之前,我想首先和大家聊聊当前最热的词汇之一:“数据驱动”。 双11就要到了,当你打开手淘页面,你会收到平台推荐给你的优惠活动信息,你可能感兴趣的商家或者商品, 你随意地...

袋鼠云
11/09
0
0
曾经踩坑党,如今护航忙 | 袋鼠云的双11故事之一

普通人提起双11,谈的都是剁手党 袋鼠云提起双11,谈的却是踩坑党 每年双11,同样的通宵达旦、同样的激动万分、同样的心跳加速,同样的肾上腺素增加,不一样的是:剁手党在Happy,踩坑党在忧...

袋鼠云
2017/11/09
0
0
数据中台助力传统企业数字化转型

在2018云栖大会·上海峰会零售合作伙伴专场上,袋鼠云技术总监张旭为现场听众带来了题为《数据中台助力传统企业数字化转型》的分享,分享中他以茅台集团为例,详细讲解了数据中台是如何助力茅...

笑傲江湖lcx
06/19
0
0
数智前沿 | 重庆智博会&云栖大会:袋鼠云携手国酒茅台亮相,就是要给你好看!

数智前沿 Column No.2 @2018重庆智博会&云栖大会 山城重庆又双叒叕火了 近日,重庆人民的朋友圈里 《延禧攻略》让了位 各种酷炫“黑科技”霸了屏, 都是因为这件大事—— 8月23-26日 首届中国...

袋鼠云
08/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Confluence 6 教程:在 Confluence 中导航

当你对 Confluence 有所了解后,你会发现 Confluence 使用起来非常简单。这个教程主要是针对你使用的 Confluence 界面进行一些说明,同时向你展示在那里可以进行一些通用的任务和操作。 空间...

honeymose
7分钟前
1
0
sed, awk 练习

1. sed打印某行到某行之间的内容 2. sed 转换大小写 将单词首字母转化大写 将所有小写转化大写 3. sed 在某一行最后面添加一个数字 4. 删除某行到最后一行 解析: {:a;N;$!ba;d} :a : 是...

Fc丶
今天
2
0
babel6升级到7,jest-babel报错:Requires Babel "^7.0.0-0", but was loaded with "6.26.3".

自从将前端环境更新到babel7,jest-babel之前是基于babel6的,执行时候就会报:Requires Babel "^7.0.0-0", but was loaded with "6.26.3". 很烦,因为连续帮好几台电脑修复这个问题,所以记...

曾建凯
今天
1
0
探索802.11ax

802.11ax承诺在真实条件下改善峰值性能和最差情况。 如何改善今天的Wi-Fi? 在决定如何改进当前版本以外的Wi-Fi时,802.11ac,IEEE和Wi-Fi联盟调查了Wi-Fi部署和行为,以确定更广泛使用的障碍...

linuxprobe16
今天
2
0
使用linux将64G的SDCARD格式化为FAT32

一、命令如下: sudo fdisk -lsudo mkfs.vfat /dev/sda -Isudo fdisk /dev/sda Welcome to fdisk (util-linux 2.29.2). Changes will remain in memory only, until you decide to wri......

mbzhong
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部