28动态规划

动态规划

一般问题形式：求最优值

基本思想：将待求解的问题分解成若干子问题，对子问题进行求解。

一般适合DP求解的问题，子问题不独立。

将已经解决的子问题的解保存，当需要用到该子问题时，直接使用答案，避免重复计算。

包含的基本要素

1.最优子结构

2.重叠子问题

解决方法

1.动态规划表（自底向上）

2.备忘录（自顶向下）

解决步骤

1.判定是否是一个动态规划问题

2.确定好状态（参数）

3.构建状态转移方程

4.为状态添加备忘录或DPTable