动态规划详解：从记忆化搜索到状态转移方程

"DP白话文:-ACM算法之动态规划(DP) 动态规划 DynamicProgramming 东农ACM/ICPC集训队 小e 制作" 动态规划（DP）是一种优化技术，源自运筹学，常用于解决多阶段决策过程中的最优化问题。由美国数学家R.E.Bellman在20世纪50年代提出，它通过将复杂问题分解为较小的子问题来求解全局最优解。动态规划的核心特点是避免重复计算，通过存储和重用先前计算的结果来提高效率。 DP不仅仅是单一的算法，而是包含了分治和递归两种基础算法思想的综合应用。当一个问题具有重叠子问题和最优子结构时，通常适合采用动态规划来解决。最优子结构意味着问题的最优解可以通过其子问题的最优解来构造。 在实际应用动态规划时，一般遵循以下步骤： 1. **定义状态**：首先，我们需要定义问题的状态，例如在数字三角形问题中，状态可以表示为到达某一层某一点的最大路径和。 2. **确定状态转移方程**：找到从一个状态转移到另一个状态的关系，这通常是问题的关键。在数字三角形问题中，状态转移方程为 `f(i, j) = min{f(i+1, j), f(i+1, j+1)} + triangle[i][j]`，其中 `f(i, j)` 表示到达第 `i` 层第 `j` 个节点的最小路径和，`triangle[i][j]` 是该节点的权值。 3. **边界条件**：设置初始状态，通常是问题的最简单情况。对于数字三角形问题，边界条件是顶层的每个节点，其路径和即为其自身的值。 4. **状态枚举**：从边界条件开始，按照状态转移方程逐步计算出所有状态的值，通常是从底层向上或从简单状态向复杂状态进行。 5. **记忆化搜索**：动态规划经常通过记忆化搜索来实现，即将已计算过的状态值存储下来，避免了重复计算。在有限的空间内，牺牲一定的内存来换取计算时间的显著减少。 动态规划在ACM/ICPC等算法竞赛中非常常见，因为它能有效地解决许多复杂问题，如背包问题、最长公共子序列、最短路径等。理解并熟练运用动态规划是提升算法能力的关键。通过不断实践和分析问题，你可以逐渐掌握这种强大的解决问题的方法。