节节高升 蓝桥杯模拟-爱代码爱编程
【问题描述】
小蓝要上一个楼梯,共
15
级台阶。
小蓝每步可以上
1
级台阶,也可以上
2
级、
3
级或
4
级,再多就没办法一步走到了。
每级台阶上有一个数值,可能正也可能负。每次走到一级台阶上,小蓝的得分就加上这级台阶上的数
值。台阶上的数值依次为
: 1, 2, 1, 1, 1, 1, 5, 5, 4, -1, -1, -2, -3, -1, -9
。
小蓝希望不超过
6
步走到台阶顶端,请问他得分的最大值是多少
?
注意,小蓝开始站在地面上,地面没有分值。他最终要走到台阶顶端,所以最终一定会走到数值为
-9
的 那级台阶,所以 -9
一定会加到得分里面。
思路:dfs(stair,step,score),stair是现在所在的楼梯数,step是走了几步,score是目前得分。每次stair+(1,2,3,4)中的任意一个,step+1,score+stair对应的分数,逐层遍历,求得最大值
maxq = -100000#用来记录最大值
a = [0,1,2,1,1,1,1,5,5,4,-1,-1,-2,-3,-1,-9]
def dfs(stair,step,score):
if step>6:#超过6步,重新开始下一个循环
return
if stair==15:#到达楼梯顶端 记录这次的score和以前最大值maxq哪个更大,更新最大值
global maxq
maxq=max(score,maxq)
return
for i in range(1,5):#只能走一到四步
if stair+i<=15:
dfs(stair+i,step+1,score+a[stair+i])
dfs(0,0,0)
print(maxq)