动态规划:青蛙跳台阶问题
程序员文章站
2023-12-21 20:25:23
...
问题描述:青蛙可以一次跳一个台阶,也可以一次跳两个台阶,总共有10层台阶,青蛙有多少种选择
动态规划:设第n层的最多选择为Stage(n),根据题意,可得如下状态转移方程:
Stage(n)=Stage(n-1)+Stage(n-2)
如果n=10,则上述的意思就是第十层的选择等于第九层的选择数+第八层的选择数。(这是因为青蛙一次可以跳一个台阶,也可以一次跳两个台阶,当青蛙在第八层和第九层时都可以达到第十层)
def Stage(n):
if n<0:
return -1
elif n==0:
return 0
elif n==1:
return 1
elif n==2:
return 2
else:
dp=[]
dp.append(0)
dp.append(1)
dp.append(2)
for i in range(3,n+1):
dp_tmp=dp[i-1]+dp[i-2]
dp.append(dp_tmp)
return dp[n]
print(Stage(10))