第31929题 单选题
已知爬楼梯问题规则为：每次可以爬1阶或者2阶台阶，求爬到第n阶台阶总共有多少种不同的方法。下列用C++动态规划实现该问题的相关说法中，正确的是？
A

状态转移方程可以定义为dp[i] = dp[i-1] + dp[i-2]，其中dp[i]表示爬到第i阶的方法数，初始条件为dp[1] = 1，dp[2] = 2

B

该问题的动态规划实现空间复杂度最低为O(n)，无法进一步优化

C

该问题只能用自底向上的递推方式实现动态规划，不能用记忆化搜索实现

D

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

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