第30895题 单选题
以下关于C++实现爬楼梯动态规划算法的描述中，错误的是？

爬楼梯问题规则为：每次可以选择走1阶或者2阶台阶，计算爬到第n阶台阶的总方案数，是动态规划入门经典场景。

A

状态转移方程可以定义为dp[i] = dp[i-1] + dp[i-2]，含义是到第i阶的方案数等于到i-1阶走1步、到i-2阶走2步的方案数之和

B

动态规划的初始条件通常设置为dp[1] = 1，dp[2] = 2，当n=0时可特殊处理为1

C

该问题的动态规划实现只能使用O(n)的空间复杂度，无法进一步优化

D

如果使用自底向上的动态规划实现，可以避免递归版本的重复计算问题，时间复杂度为O(n)

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