《算法的乐趣》第十二节

本节讲解动态规划的后两个设计步骤：定义决策与状态转换方程，以及确定边界条件。

本节讲解动态规划的后两个设计步骤：定义决策与状态转换方程，以及确定边界条件。决策是使阶段结果最优的动作，状态转换方程描述相邻阶段的演化规律；若状态定义不当导致子问题无重叠，算法就会退化成朴素递归搜索。文中以装配站、背包、最长公共子序列三个问题为例，分别给出各自的决策方式与状态转换方程；边界条件在记忆搜索中即递归终结条件，在递推实现中则是递推的初始值，同样给出了三个问题的边界。

随后以字符串编辑距离为例演示完整设计过程：用插入、删除、替换三种操作将一个串变为另一个串，最少操作次数即编辑距离。朴素递归算法复杂度为O(3^n)，长度5的字符串即需递归241次。定义状态d[i,j]为源串前i个字符转为目标串前j个字符的最少编辑次数，用二维备忘录记录各状态，递归次数降到40次，复杂度接近O(n²)。再给出递推形式的递推关系（两字符相等时不变，不等时取三种操作的最小值）与边界条件（任一串为空时距离等于另一串长度），实现直接递推动画法。

最后引入解空间的穷举搜索：解空间是全部候选解构成的有限集合，穷举即按一定策略逐一枚举并检验。其基本步骤是：定义解、解空间范围与正确解判定条件；再依解空间特点选择搜索策略并配合剪枝。解空间的结构可能是线性表、集合、树或图，其定义取决于解的数学模型——以0-1背包为例，把解定义为物品选择状态的n元组比定义为价值总和更便于设计搜索算法。