第31918题 单选题
使用动态规划求解爬楼梯问题(n阶楼梯,每次可爬1或2阶,求爬到楼顶的总方案数),当n=5时,相关描述正确的是?

已知动态规划问题通常包含状态定义、转移方程、初始状态三个核心要素,爬楼梯是典型的入门级动态规划场景。

A

总方案数为8,dp[i]定义为爬到第i阶的总方案数,转移方程为dp[i] = dp[i-1] + dp[i-2],初始状态dp[1]=1、dp[2]=2

B

总方案数为5,dp[i]定义为爬i次到达楼顶的方案数,转移方程为dp[i] = dp[i-1] + 2,初始状态dp[1]=1

C

总方案数为13,该问题用动态规划求解的时间复杂度为O(2^n),空间复杂度必然为O(n)

D

该问题无法用动态规划求解,只能用递归暴力枚举所有可能的爬楼方案

程序运行统计
暂无判题统计
提交0次 正确率0.00%
答案解析