单选题
适中
#16961
以下关于动态规划的说法中,错误的是( )。
以下关于动态规划的说法中,错误的是( )。
答案与解析
正确答案:B
解析
动态规划通过定义状态描述问题的子结构,建立状态之间的转移关系形成递推公式。状态数量决定计算过程中需要处理的子问题总数。实现时可采用自底向上的递推方式,按顺序求解每个状态;也可采用自顶向下的递归方式配合记忆化存储,避免重复计算相同状态。两种实现方式均覆盖全部必要子问题,访问的状态集合一致,执行的操作规模由状态空间和转移成本共同决定。算法的时间开销取决于状态总数与单个状态转移所需时间的乘积。