在动态规划问题中,“状态转移方程+递推”和“递归+记忆化搜索”通常是解决同一问题的两种不同实现方式,它们的时间复杂度总是相同的。( )
A:正确
B:错误
正确答案:错误
答案解析
分析动态规划中状态转移方程与递推的实现机制,明确其通过迭代方式按序计算各状态值的过程;分析递归与记忆化搜索的实现机制,明确其以递归调用为基础,在搜索路径中存储已计算状态值的方式;比较两者在处理相同状态空间时的计算次数与访问频率;考察时间复杂度是否由状态总数和每个状态的计算耗时共同决定;确认两种方法在状态计算次数和重复子问题处理上的一致性。
试卷来源:202603 CCF-GESP编程能力等级认证C++八级真题