第31931题 单选题
关于C++实现动态规划经典爬楼梯问题，下列说法正确的是？

爬楼梯问题定义：给定正整数n代表楼梯总阶数，每次仅可向上走1阶或2阶，要求返回爬到第n阶的不同方法总数。

A

该问题的动态规划状态转移方程可定义为dp[i] = dp[i-1] + dp[i-2]，边界条件为dp[1] = 1，dp[2] = 2

B

使用普通递归实现该问题的时间复杂度为O(n)，效率高于动态规划实现

C

C++实现该问题的动态规划解法必须使用长度为n的dp数组，无法将空间复杂度优化到O(1)

D

该问题不满足动态规划的重叠子问题性质，因此不适合使用动态规划求解

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