用代码实现:动态规划法解题:有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。
时间: 2024-05-28 20:15:34 浏览: 130
一个简单的动态规划示例
可以使用动态规划的思想解决这个问题。
定义dp[i]表示到达第i级台阶的方法数,那么可以得到动态转移方程:
dp[i] = dp[i-1] + dp[i-2]
其中dp[1] = 1, dp[2] = 2。
最终答案为dp[n]。
可以使用python代码实现:
def climbStairs(n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(climbStairs(5)) # 输出结果为8,即有8种不同的方法可以走完5级台阶。
阅读全文