判断题
偏易
#16720
在动态规划问题中,状态空间相同且没有重复计算的情况下,“状态转移方程+递推”与“递归+记忆化搜索”的时间复杂度通常相同。
在动态规划问题中,状态空间相同且没有重复计算的情况下,“状态转移方程+递推”与“递归+记忆化搜索”的时间复杂度通常相同。
答案与解析
正确答案:对
解析
比较两种实现方式的时间复杂度需分析其基本机制。状态转移方程配合递推按确定顺序遍历状态空间,每个状态仅计算一次。递归结合记忆化搜索在访问某状态时若未计算则求值并存储,后续直接查表。两者均保证每个状态被处理且仅被处理一次。时间消耗主要来自状态数量及单个状态的转移开销。只要状态空间一致且无冗余计算,执行的操作总量由状态数和转移关系决定,与实现形式无关。算法结构差异不影响总操作次数的理论下限。