建立动态规划状态转移方程的练习
这篇文章通过LeetCode上的八个经典题目，生动演示了如何攻克动态规划中最核心的一步：建立状态转移方程。作者从自身的复习笔记出发，挑选了Word Break、Unique Paths、Edit Distance等覆盖字符串、网格、树结构等多个领域的典型问题，逐一拆解其思考过程。 文章的核心观点是，解动态规划题的本质在于“状态识别”和“状态转移方程建立”这两步。像循环与递归的选择、空间换时间的优化，都只是实现技巧而非核心。例如，在解“三角形最小路径和”时，关键在于定义从底层向上积累的最短路径值f(i, k)，并建立f(i, k) = min(下一层相邻状态) + 当前值的递推关系。对于“交错字符串”问题，则需定义f(i, j)表示两个子串前缀能否形成目标前缀，并据此建立逻辑或的转移方程。 作者没有停留在给出公式，而是试图还原每道题背后的状态定义逻辑。这种从具体例子提炼通用思考方法的叙述，让抽象的“建立方程”变得可触摸。对于正在学习动态规划的人来说，跟随这八个问题的思路走一遍，能有效训练如何从问题描述中提取状态，并找到状态之间递推关系的“感觉”。