第31919题 单选题
以下关于爬楼梯问题（每次可以走1阶或2阶，求走到第n阶的总方法数）的C++动态规划实现描述，正确的是？

已知爬楼梯问题规则为每次只能向上走1阶或者2阶台阶，求走到第n阶台阶的总方案数，采用动态规划思路求解。

A

dp数组的含义可以定义为dp[i]表示走到第i阶台阶的总方案数，状态转移方程为dp[i] = dp[i-1] + dp[i-2]，边界条件dp[1]=1，dp[2]=2

B

动态规划解决该问题的时间复杂度是O(2^n)，和暴力递归解法效率一致

C

该问题只能用动态规划求解，无法采用其他算法得到正确结果

D

状态转移方程必须写成dp[i] = dp[i+1] + dp[i+2]，从后往前推导才能得到正确结果

程序运行统计
暂无判题统计
知识点：
C++算法实现-动态规划基础
提交0次 正确率0.00%
答案解析
上一题 下一题