【问题描述】
小蓝要上一个楼梯，共
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)
