在我们写题中，总会遇到深搜和广搜超时的情况，这样就需要一个新的算法来帮助我们，那就是——动态规划
目录
动态规划介绍
例题
1、最优化子问题
2、不影响后续决策
点赞+关注！
动态规划介绍
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。
动态规划，英文是Dynamic Programming，简称DP，擅长解决“多阶段 决策问题”，利用各个阶段的递推关系，逐个确定每个阶段的最优决策，并最终得到原问题的最优决
例题
蒜头君要回家，已知蒜头君在 (1,1) 位置，家在 (n,n) 坐标处。蒜头君走到一个点 (i,j) 会花费一定的体力 aij ，而且蒜头君只会往家的方向走，也就是只能往上，或者往右走。蒜头君想知道：他 回家需要花费的最少体力 是多少。
例如下表所示，格子中的数字代表走到该格子花费的体力：
对于该表来说，共花费体力为：3+2+4+3=12。
| 5 | 4 | 3（家） |
| 6 | 2 | 5 |
| 蒜头君 | 3 | 4 |
我们把走到一个点看做一个状态，走到一个点只有两种方式 ，一个是 从下面走到该点 ，
一种是 从左边走到该点 。那么点 (i,j) 要么是从 (i−1,j) 走到 (i,j)，要么是从点 (i,j−1) 走到所以从哪个点走
到 (i,j) 就是一个决策，我们用 dp(i,j) 来代表走到点 (i,j) 一共花费的最少体力。
我们需要花费最少力气走到家，所以可以得到状态转移方程：
dp(i,j)=min( dp(i−1,j) , dp(i,j−1) )+ a ij
根据转移方程我们可以推出走到每个点花费的最少体力。
可以看出来，动态规划算法的核心是DP方程。
所以说，状态转换方程（DP方程）就是算法的核心，那么设计DP方程，要有什么注意的呢？以下列出来几点！
1、最优化子问题
从上面的算法三要素中，可以看出，dp方程是最优子问题中归纳而来的。什么才 是“最优子题”呢？不管之前决策是否是最优决策，都必须保证从现在开始的 决策是在之前的基础上最优。具体说我们默认dp1和dp2就是最优的，在此基 础上，得到最优的dp3。
2、不影响后续决策
由于上一条我们看到，如果dp1的决策会影响到dp2和dp3的决策，那么dp3 = dp2+dp1就不成了，所以，要一定保证，每个阶段的决策仅受之前决策的影响，但不影响之后阶段的决策
点赞+关注！
相关作品：mjyleon的博客系列作品
