动态规划

动态规划（Dynamic Programming，DP）比较困难的原因，是类型多，无固定模板，灵活多变。作为一种制表法，入门时强烈建议制表画图来辅助理解，对动态规划问题非常重要的状态定义。

动态规划问题的特点

• 最优子结构：大问题分解为小问题，小问题最优来决策大问题最优
• 子问题重叠：子问题互相可能不独立，将会有多次重复
• 无后效性：未来只由过去进行计算

需要慢慢学会分辨动规类问题。如：

规定只能向下走和向右走

设问 1：从 a 到 b 问有多少种走法。

设问 2：从 a 到 b 输出所有路径。

以上两个问题，哪个更可能是动态规划类问题？

{{ select(1) }}

• 问题1
• 问题2

可以注意到，问题 1 最终只关心走法总数，对具体怎么走并不关心。而问题 2 会关心所有的路径。可以想象，当这个图很大时，关于问题 2 的处理将会非常耗时。而问题 1 呢？

动规类问题很多时候，只关心最终的结果，和与结果有直接关联的操作

1. 确定状态：尝试设计 f(i, j) 表示从 (1, 1) 到达 (i, j) 的路径总数。

2. 划分阶段：从最后一步进行分析，

   若最后一步从上来：f(i - 1, j) 表示从 (1, 1)->(i - 1, j) 的路径总数，往下走一步到达 f(i, j)。

   若最后一步从左来：f(i, j - 1) 表示从 (1, 1)->(i, j - 1) 的路径总数，往右走一步到达 f(i, j)。

   将两个种类数计数相加即可。

3. 状态转移方程：

   $$f(i, j) = f(i - 1, j) + f(i, j - 1);$$

4. 初始化边界： 考虑到状态 i >= 1, j >= 1，且第一行第一列的路径总数只能是 1，因此

   $$f(i, j) = \left\{ \begin{aligned} & f(i - 1, j) + f(i, j - 1) & & i, j > 1 \cr & 1 & & i = 1 \ or \ j = 1 \end{aligned} \right. $$

5. 计算顺序：根据转移方程，显然符合无后效性 (过去计算未来) ，则构造记忆递归自顶向下 (解决子问题重叠) 或循环递推自底向上 (制表法) 都行。

👉路径计数

后话

动态规划类问题无固定模板，对于状态的感知非常依赖经验，因此多做题是最实际的办法。

多年以来，虽动规类问题灵活多变，但总结下来常见类动规也可以有

• 序列型动规
• 坐标型动规
• 最长序型动规
• 博弈型动规
• 背包型动规
• 区间型动规
• 数位型动规
• 状态压缩动规
• 树上动规
• 图上动规
• 综合类动规（无明显特征，需要不断进行拆解分析）

需要极大的耐心和细心进行训练。