动态规划详解：状态与决策

"动规的要诀－状态-浙江大学_acm程序设计竞赛_动态规划讲义" 动态规划是一种重要的算法，尤其在ACM程序设计竞赛中是必不可少的技能。它以其灵活性和广泛应用受到出题者的青睐。动态规划的核心在于定义和处理状态，通过状态转移方程来求解最优化问题。 首先，我们要理解动态规划与搜索的关系。动态规划可以看作是优化后的记忆化搜索。在解决数字三角形问题的例子中，我们需要找到一条路径，使得路径上的数字之和最小或最大。这是一个典型的动态规划问题，状态可以定义为到达三角形某位置的最小（或最大）和，即f(i, j)表示到达第i层第j个位置的最优和。状态转移方程为f(i, j) = a[i, j] + min{f(i - 1, j), f(i - 1, j + 1)}，表示当前位置的最优和是当前元素值加上上一层相邻位置的最小最优和。 然而，当问题复杂度增加，直接写出循环式的动态规划可能变得困难。这时，我们可以采用记忆化搜索来简化问题。记忆化搜索是动态规划的一种直观表示，通过保存已经计算过的子问题答案（存储在opt数组中），避免重复计算，从而提高效率。例如，在数字三角形问题中，我们可以维护一个二维数组opt[i][j]来存储f(i, j)的值，当需要计算f(i, j)时，直接从opt数组中查找，而不是重新计算。 动态规划的关键在于状态的定义和状态转移方程的建立。状态通常是指问题在某一阶段的完整描述，它可以是问题的一个实例、一个组合特征或者一个中间结果。状态转移方程则描述了从一个状态转移到另一个状态的过程，它定义了解决问题的步骤。 此外，动态规划还有多种类型和变种，例如： 1. 状态阶段决策：在某些问题中，状态可能会经历多个阶段，每个阶段都有相应的决策，我们需要在每个阶段找到最优决策，从而达到全局最优。 2. 确立状态的方法：可以通过问题的结构、约束条件或者问题的性质来确定状态。例如，斐波那契数列中的状态可以是前两个数，背包问题中的状态可以是当前物品的选择情况和剩余容量等。 3. 简单的动规武器：包括最短路径问题（如Floyd-Warshall算法）、最长公共子序列、矩阵链乘法等，它们都基于特定的状态定义和状态转移规则。 4. 特殊的动态规划：例如，带有剪枝的动态规划，用于减少无效的计算；多层次动态规划，适用于解决多阶段决策问题；还有滚动数组技术，用于节省空间。 动态规划在实际问题中的应用广泛，不仅限于ACM竞赛，也常见于计算机科学的许多领域，如图论、组合优化、字符串处理等。熟练掌握动态规划的要诀，能够帮助我们更有效地解决复杂问题。