1 动态规划

1.1 定义

动态规划的核心是状态和状态转移方程。

在记忆化搜索中，可以为正在处理的表项声明一个引用，简化对它的读写操作；

动态规划解决的是多阶段决策问题；

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

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

动态规划问题一般由难到易分为一维动态规划，二维动态规划，多维动态规划，以及多变量动态规划问题。其中多维动态规划问题又可以进行降维。动态规划问题求解的最重要的一步就是求解出 状态转移方程

1.2 特性