首页 > 试题广场 >

关于动态规划，下列说法错误的是_______。

[单选题]

使用动态规划的两要素是“最优子结构”和“重叠子问题”

在使用“cut-and-paste”技术证明最优子结构时，要求子问题之间是相互关联的

若子问题空间大小为多项式阶，则动态规划的时间一般也是多项式的

一般情况下，动态规划和其记忆型递归的变种算法的渐进时间相同

HackerLzh

a对

b对，动态规划要求子问题之间要相互关联，而贪心算法不要求

c错，时间和空间能有什么关系！？前面应该改成“子问题时间大小”

d对，记忆型递归应该就是备忘录算法吧，那确实和动态规划时间复杂度一样。

编辑于 2023-01-28 17:34:21 回复(0)

lusyang

发表于 2017-11-27 14:34:37 回复(1)

提交观点

问题信息

动态规划

上传者：阿奻_

难度：

2条回答 4收藏 7589浏览

扫一扫，把题目装进口袋