计算机算法设计与分析——算法思想综述CharlieODD

一个喜欢live、渴望自由、积极躺平的小小打工人

（2）分治：分治的设计思想是将一个规模为n难以解决的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题同样。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

（1）动态规划过程是：依据当前（阶段）状态，採取对应的决策，引起状态的转移。例如以下图，一个决策序列就是在变化的状态中产生出来的，这样的多阶段最优化决策解决这个问题的过程就称为动态规划。

初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

图1动态规划决策过程示意图

（3）与分治法最大的区别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。