动态规划基础¶
本页面记录了最简单、典型的几种简单动态规划题目，用作未学过动态规划的新手的入门，对这个陌生的算法有一定了解。
引入¶
例题¶
数字三角形
有一个 \(n\) 行的数字三角形，第 \(i\) 行正好有 \(i\) 个数。现在你需要找到一条从第一行走到第 \(n\) 行的路径，每一个地只能跳到下一行的正下方或者后下方的点，你需要求出最大路径和。
思考¶
我们可以使用学过的搜索算法尝试进行求解。可是，对于任意一个点，有两种决策，那么时间复杂度就是 \(\mathcal O(2^n)\) 的，如果 \(n\) 过大，那么这个算法很显然会超时。
这时，我们发现了一个规律：对于同一个结点结束的路径，我们只有取最大值才会在后面的转移中做到最优。因此，我们直接对状态进行分组，用 \((i,j)\) 表示为现在到达了 \(i\) 行 \(j\) 列。对于每一个分组，我们都需要取最大值，这样子才能求出正确的解。
这就是动态规划问题的基本思路。
原理¶
动态规划的题目一般具有最优子结构、无后效性和子问题重叠。
最优子结构¶
可以通过多个最优的子问题来构造出一个最优的答案，因此我们就可以先求简单的子问题，然后一步一步推出整个问题的答案。
无后效性¶
这个是 dp 的一个非常重要的点。对于一个已经完成了的选择，这个选择不会影响后面的其他选择。
子问题重叠¶
其实就是状态分组，将很多重叠的子问题存进一个最优的 dp 数组里面，就可以避免重复求解。
通常思路¶
- 第一步：首先将原问题分成若干个不同的阶段，每一个阶段对应了很多的子问题，得出状态；对状态进行化简，使得状态既不繁琐、又能完整地表示出所有信息。
- 第二步：重点需要找对于每一个状态我们需要做什么决策，做好状态之间的转移，也就是找到状态的转移方程。
- 第三部：根据一定的拓扑序求解每一个阶段的子问题，最后求出最终的答案。