动态规划(Dynamic Programming)
描述
- 每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划.
- 将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最
一个子问题就是初始问题的解.
- 能采用动态规划求解的问题的一般要具有3个性质:
(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
(3) 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
- 基本步骤
(1) 分析最优解的性质，并刻画其结构特征。
(2) 递归的定义最优解。
(3) 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
(4) 根据计算最优值时得到的信息，构造问题的最优解
公式
1.dp[i] = dp[i-1]+f(i)
2.dp[i][j] = dp[i][k] + dp[k+1][j] + f(k)
3.
问题
1. 矩阵连乘
2. 走金字塔
3. 最长公共子序列(LCS)
4. 最长递增子序列(LIS)
5. 凸多边形最优三角剖分
6. 背包问题
7. 双调欧几里得旅行商问题
8. 鹰蛋问题
9. 最大子段和问题