跳到主要内容

动态规划

先观察问题是否适合使用回溯(穷举)解决

适合用回溯解决的问题通常满足“决策树模型”,这种问题可以使用树形结构来描述,其中每一个节点代表一个决策,每一条路径代表一个决策序列。

换句话说,如果问题包含明确的决策概念,并且解是通过一系列决策产生的,那么它就满足决策树模型,通常可以使用回溯来解决。

在此基础上,动态规划问题还有一些判断的“加分项”。

  • 问题包含最大(小)或最多(少)等最优化描述。
  • 问题的状态能够使用一个列表、多维矩阵或树来表示,并且一个状态与其周围的状态存在递推关系。

相应地,也存在一些“减分项”。

  • 问题的目标是找出所有可能的解决方案,而不是找出最优解。
  • 问题描述中有明显的排列组合的特征,需要返回具体的多个方案。

如果一个问题满足决策树模型,并具有较为明显的“加分项“,我们就可以假设它是一个动态规划问题,并在求解过程中验证它。