动态规划
动态规划思想
将一个规模为n的问题分解为k个规模较小的子问题，但这些子问题不是互相独立的，前一个子问题的解，对后一个子问题的解有影响
动态规划问题的求解过程是多阶段决策的过程，每一步处理一个决策。常用于求最优解的问题。
注意：这里问题是由多个阶段的“决策”组成，而不是“问题”。这两者还是有细微差别的。
这里为了方便解释，举例说明：
这里参考【北大公开课】算法设计的例子 https://www.bilibili.com/video/av7134874?p=36
这是一个求最短路径的问题，要求从S点走到T点的路径最短。（任意S到任意T，只能向右走）
解：
- 我们可以把一个大问题划分为多个子决策的组合，这些子决策拥有相同的等级；在这里，大的决策是从S走到T，我们可以把这个大决策化解为S到A，A到B，B到C，C到T；
- 与通常的思路不同，我们并不是从起点开始阶段，而是从终点向前推进，找出每一个子决策的最优解
最终可以计算得出结果如下图：
动态规划解决了什么问题
动态规划通常用于解决包含了多个阶段决策的最优解问题。
使用动态规划的条件
具有最优子结构性质：一个最优决策序列的任何子序列，也一定是一个最优决策序列。
动态规划方向性
首先要理解“后边界不变，前边界前移”，参考本文刚开始举出的最短路径的例子，解决子问题的顺序是从终点到起点的。
算法实例
- 背包问题
- 矩阵连乘