五大类算法中的动态规划

一、基本概念

在动态规划的过程中（也就是所谓的DP过程中），每一次决策都基于当前的状态（即上一步的结果），并随之导致状态的转移（即下一步的状态）。由不断变化的状态所形成的决策序列即为此类多阶段优化问题所采用的解决方式（也就是所谓的策略选择），并且通过一系列这样的最优选择构成了整个问题的最佳解决方案（也就是所谓的全局最优解）。因此，在这样的多步骤优化问题中（也就是所谓的多目标优化问题中），通过将各个阶段的问题有机结合起来而形成的方法被称为动态规划方法（即DP方法）。

二、基本思想与策略

基本思路类似于分治法，在解决问题的过程中同样地，在解决问题的过程中将待解决的问题分解成为多个独立的部分进行逐一分析和处理；每个部分都按照一定的顺序被解决，并且每个部分的答案都会为后续部分提供必要的信息来进行下一步的操作；在整个过程中需要综合考虑所有可能出现的情况并做出相应的决策筛选出那些可能导向全局最优的结果；最终通过逐步解决每一个具体的问题从而最终得到最初的整体解决方案

由于动态规划通常用于解决具有重叠子问题的问题，在这种场景下设计算法以减少冗余计算。为了实现这一目标，在处理每个子问题时只需求解其一次，并将各个阶段的不同状态存储在一个二维数组中。

与分治法最大的区别在于：能用动态规划方法解决的问题在其分解后的各个子问题之间通常具备非独立性（即后续阶段的问题通常依赖于前一阶段