Skip to content

动态规划

待复习的内容：

  • 5-bullet-point structure for presenting dynamic programming solutions
  • 作业中出现过的DP题
  • 课程中出现过的DP题

Sequence DP: Climbing Stairs, House Robber

2D DP: Union Paths, Paint House

动态规划思想

动态规划的核心思想就是把大问题分解成 小问题 ，并通过存储和重用小问题的解来避免重复计算，从而高效地解决 大问题 。

如果一个问题的最优解包含其子问题的 最优解 ，那么这个问题就具有最优子结构（Optimal Substructure）性质。

  • 例子： 假设我们要找从 A 到 C 的最短路径。如果 B 是 A 到 C 的最短路径上的一个点，那么 A 到 B 的路径，以及 B 到 C 的路径，都必须分别是它们各自的最短路径。

在分解大问题的过程中，如果同样的子问题被多次计算，那么这个问题就具有重叠子问题（Overlapping Subproblems）性质。

  • 例子： 计算斐波那契数列 \(F(n)\)。计算 \(F(5)\) 需要计算 \(F(4)\) 和 \(F(3)\)；计算 \(F(4)\) 又需要计算 \(F(3)\) 和 \(F(2)\)。可以看到 \(F(3)\) 被重复计算了。

Memoization（自顶向下）

大问题开始，递归地分解为子问题。在计算每个子问题之前，先检查它的解是否已经被计算并存储。

  • 过程：
  • 定义递归函数来解决问题。
  • 使用一个查找表（如数组或哈希表）来存储子问题的解。
  • 在递归函数开始时，检查查找表：如果已存储，则直接返回；否则，计算解，存储到表中，然后返回。

Tabulation（自底向上）

从最小的子问题开始，逐步向上计算，直到最终解决原始问题。

  • 过程：
  • 确定状态（子问题）的定义。
  • 建立一个表格（通常是数组 dp[]），用于存储所有子问题的解。
  • 确定 基准情况 (Base Cases) ，填入表格的初始值。
  • 通过 状态转移方程 ，从小到大（或从前到后）依次计算并填充表格。

解题步骤

对于动态规划问题，基本都可以用以下步骤来解决：

  1. 确定子问题，如在背包问题中，子问题就是dp[i][j]
  2. 确定base case，如在斐波那契数列中，dp[0]=0, dp[1]=1就是base case
  3. 确定状态转移方程，这是动态规划的核心，一旦找到状态转移方程，那么再难的题都会瞬间变成一道简单题
  4. 确定计算顺序，对于1D-DP，一般就是从0到n；对于2D-DP，通常就是按行或者列递增

Sequence DP

序列DP（Sequence DP）：这类问题通常在一个一维序列上进行操作，状态 \(DP[i]\) 依赖于序列中靠前的元素。

斐波那契数列

最长递增子序列（LIS）

Kadane's最大子数组和

最大乘积子数组

打家劫舍

Two-Sequence DP

这类问题处理两个序列之间的关系，状态 \(DP[i][j]\) 表示第一个序列的前 \(i\) 个元素和第二个序列的前 \(j\) 个元素形成的最优解。

最长公共子序列（LCS）

Edit Distance

Interval DP

最长回文子序列

最长回文子串（LPS）

RNA Folding

矩阵链乘法

Knapsack DP

0/1背包问题

Coin Changing

完全背包

多重背包

2D-DP

Unique Paths

三角形最小路径和

Tree DP

Bitmask DP

Digital DP

Game DP

博弈DP涉及两个或多个玩家采取最优策略，状态转移通常体现了最大化自己的收益、最小化对手收益的博弈过程。

Coin Game

假设有一排共 \(n\) 枚硬币，它们的价值由一个数组 \(A = [v_1, v_2, \ldots, v_n]\) 表示，其中 \(v_i\) 是第 \(i\) 枚硬币的价值。给定 \(n \in \mathbb{N}\) 且 \(n\) 是一个 偶数 。

两位玩家（Player 1 和 Player 2）轮流从这排硬币中取走一枚硬币。Player 1 先开始。在每一轮中，当前玩家必须选择取走最左边或最右边的硬币，并将其价值计入自己的总得分。

两位玩家都采用 最优策略 ：他们都会最大化自己的最终总得分（即最大化自己相对于对手的收益）。

目标： 设计一个算法，确定 Player 1 在这种最优对弈下可以获得的 最大保证收益 （Maximum Guaranteed Payoff）。

我们将使用动态规划来解决此问题。定义 \(MAX\_GAIN(i, j)\) 为：当只剩下数组 \(A\) 的子数组 \([v_i, v_{i+1}, \ldots, v_j]\) 时（该子数组的长度 \(j - i + 1\) 必须是一个正偶数），当前玩家能够获得的 最大保证收益 。

解：

这道题是我在学校上算法课时印象最深的一道题，花了很久都没有做出来，我们来一起看一下这道题。

首先回顾一下规则：

  • 有一排硬币，由数组A表示，长度为n，n是一个偶数，每个硬币都有价值
  • 每次只能拿最左边或者最右边的硬币
  • 两人轮流拿，Player1先开始
  • 两人的目标都是最大化自己的总价值

这道题最难的地方在于：两个人都想最大化自己的总价值，于是构成了一个博弈问题。每个人在选择的时候，都要同步思考：我一步后，会给对手留下什么样的残局？对手会如何利用这个残局来最大化收益？

举例来说：

\[ A = [10, \quad 5, \quad 1, \quad 100] \]

很显然，P1一定会先拿100，因为如果P1拿10，P2就能拿到决定胜负的100，因此P1一定会拿100。P1拿了100后，P2一定会拿10，进而P1一定会拿5，最后P2拿1。

可以看到，在任何一轮中，A一定会拿可以让自己最终得到最大收益的那一个子，即：

\[ MAX\_GAIN = \max \left\{ \text{拿左边路径}, \quad \text{拿右边路径} \right\} \]

但是如果硬币多了怎么办呢？我们把硬币数量增加一些：

\[ A = [10, 5, 1, 100, 20, 50, 90, 100, 80, 30, 100, 30, 5, 10, 5, 10] \]

很显然，完全无法一眼看出第一步P1应该取走哪一边，因为整个硬币列表中出现了多个100，并没有决定性的一着。

我们来一步一步思考。令L为A的一个子情况。

先来看base case，当硬币只剩两个的时候，\(L=[v_i, v_{i+1}]\)，显然：

\[ MAX\_GAIN(i, i+1) = \max(v_i, v_{i+1}) \]

接着看剩下4个硬币的时候，\(L = [v_i, v_{i+1}, v_{i+2}, v_{i+3}]\) ，此时P1无论选左边还是右边，P2都一定会选择那个让自己拿最多的，也就是说，如果P1拿走了vi，那么P2要么拿走vi+1，要么拿走vi+3；如果P2拿走vi+1，那么剩下两个就到达了base case，P1的收益为vi加上MAX_GAIN(i+1, i+2)或者MAX_GAIN(i+2, i+3)。很显然，P2会拿走让自己更多的选项，反过来讲，P1只能拿到更少的选项，从而P1的收益就成了：

\[ \text{P1拿}v_i\text{的收益} = v_i + \min \left\{ MAX\_GAIN(i+2, i+3), \quad MAX\_GAIN(i+1, i+2) \right\} \]

同理，如果P1拿走了vi+3：

\[ \text{P1拿}v_{i+3}\text{的收益} = v_{i+3} + \min \left\{ MAX\_GAIN(i+1, i+2), \quad MAX\_GAIN(i, i+1) \right\} \]

能做出上述归纳，那么本题就解决了90%了。我们有很多种归纳方法，但是上述Minimax几乎是唯一正确的归纳法，这是由这道题本身决定的。在标准的博弈论（Game Theory）中，当两个玩家都追求最大化自身收益时，使用的就是 Minimax 原则：P1和P2的目标都是最大化自己的收益。由于这是一个零和（或接近零和）博弈，P2 获得的收益越多，通常意味着留给 P1 的收益越少。因此，当 P1 在做决策时，他必须预见到：“无论我怎么走，我的对手 P2 都会从对我最不利的残局中选择对自己最有利的一步。” P1 的“最大保证收益”意味着 P1 必须假设 最坏情况发生 。在 P1 的视角下，对手 P2 的行动就是最小化 P1 的下一轮收益 (\(\min\) ）。

换句话说，对于P1来说，他的这一轮和对手的那一轮，相当于：

  1. 在自己的这一轮，最大化自己的收益，也就是\(MAX\_GAIN(i, j) = \max \left\{ \text{路径 } 1, \quad \text{路径 } 2 \right\}\)
  2. 在对方的那一轮，P1必须假设对方会采取最优策略来最小化留给 P1 的未来收益。因此，P1 必须在自己的总收益计算中计入这个 最坏情况的 \(\min\) 结果 。\(\text{路径 } 1 = v_i + \min \left\{ MAX\_GAIN(\dots), MAX\_GAIN(\dots) \right\}\)

因此，Minimax是本题的唯一解法。而一旦能写出Minimax在L=4的情况下的式子，我们就可以进一步推广到任意长度L的情况：

\[ MAX\_GAIN(i, j) = \max \begin{Bmatrix} \underbrace{v_i + \min \left( MAX\_GAIN(i+2, j), \quad MAX\_GAIN(i+1, j-1) \right)}_{\text{P1 拿 } v_i}, \\ \underbrace{v_j + \min \left( MAX\_GAIN(i+1, j-1), \quad MAX\_GAIN(i, j-2) \right)}_{\text{P1 拿 } v_j} \end{Bmatrix} \]

我们用一个二维数组（DP 表）来存储所有计算过的 \(MAX\_GAIN(i, j)\) 值，\(DP[i][j]\) 用于存储 \(MAX\_GAIN(i, j)\)，大小为\(n \times n\)。

进而我们可以给出本题的DP解：

Base Case (L=2)

\[ DP[i][i+1] = \max(v_i, v_{i+1}) \]

State Transition:

\[ DP[i][j] = \max \begin{Bmatrix} v_i + \min \left( DP[i+2][j], \quad DP[i+1][j-1] \right), \\ v_j + \min \left( DP[i+1][j-1], \quad DP[i][j-2] \right) \end{Bmatrix} \]

解题过程中，我们需要从最短的子数组子数组 \(L=2\) 开始，逐步增大长度 \(L\) 直到 \(n\)。因此在计算顺序上，外层循环控制L的长度（从 \(2\) 到 \(n\)，步长为 \(2\)）；内层循环控制起始索引 \(i\) (从 \(0\) 到 \(n-L\))，其目的在于遍历子数组所有可能的起始位置；循环内部计算j，\(j\) 是子数组的结束索引，通过i和L计算出来。

数组的长度可以记为：

\[ L = j - i + 1 \]

也就是：

\[ j = i + L - 1 \]

循环结束后，我们最终得到的结果就是：

\[ \text{Player 1 的最大保证收益} = DP[1][n] \]

.

Tic-Tac-Toe

Tic-Tac-Toe就是井字棋游戏，由于井字棋状态空间极小，我们可以把他视为一个记忆化的minimax问题，并使用动态规划求解。

定义子问题：\(MINIMAX(Board, Player)\)，其含义是给定当前的 棋盘状态 （Board）和 当前回合的玩家 （Player，X 或 O），计算在最优对弈下，该棋盘状态对当前玩家的 最终估值 （即 \(\mathbf{+1, 0, \text{或} -1}\)）。

Base Case：Minimax 递归在遇到游戏终局时停止，并返回精确的终局估值：

终局条件 返回值 含义
当前玩家获胜 \(\mathbf{+1}\) 这是当前玩家能达到的最好结果。
对手获胜 \(\mathbf{-1}\) 这是当前玩家能接受的最坏结果。
平局 \(\mathbf{0}\) 棋盘填满，无人获胜。

状态转移公式：

当前玩家（MAX Player，例如 X）总是选择能带来最大估值的下一步走法：

\[ MINIMAX(\text{Board}, \text{MAX}) = \max_{\text{Move} \in \text{Possible Moves}} \left\{ MINIMAX(\text{Board}_{\text{new}}, \text{MIN}) \right\} \]

相应的，对手玩家（MIN Player，例如O）总是选择能带来最小估值的下一步走法（最小化MAX Player的收益）：

\[ MINIMAX(\text{Board}, \text{MIN}) = \min_{\text{Move} \in \text{Possible Moves}} \left\{ MINIMAX(\text{Board}_{\text{new}}, \text{MAX}) \right\} \]

计算顺序：自顶向下的DFS搜索，结合记忆化：

  1. 从当前棋盘状态（Root 节点）开始。
  2. 递归地搜索所有可能的下一步（向下）。
  3. 直到遇到 Base Case（游戏终局）。
  4. 从终局状态开始，将 \(+1, 0, -1\) 的估值回溯（Backtrack）到父节点。
  5. 父节点根据自己是 \(\max\) 还是 \(\min\) 玩家，从子节点的返回值中选择 \(\max\) 或 \(\min\) 那个值，作为自己的估值。

上面我们提到，对手玩家总是选择最小化MAX Player的收益，这个乍一看不对，因为P2只是最大化自己的收益，并没有要最小化P1的收益，然而，在博弈论中，由于这个游戏是一个二人的零和博弈，在数学上P2最大化自己的收益就等于最小化P1的收益。

我们来定义收益：

  • \(S_1\): Player 1 的最终得分。
  • \(S_2\): Player 2 的最终得分。
  • \(T\): 游戏中所有硬币（或所有分数）的总和，这是一个常数。

由于这是零和或接近零和博弈（所有硬币最终都被分完，总和 \(T\) 是固定的）：

\[ S_1 + S_2 = T \]

从P1的视角来看，P1 必须假设 P2 会最大化 \(S_2\)。由于\(S_2 = T - S_1\)，为了最大化 \(S_2\)，P2 必须选择一个行动，使得 \(T - S_1\) 最大化，那么这也就意味着\(S_1\)的最小化。

我们对井字棋更深一步的来分析。井字棋所使用的动态规划，本质上就是用memo去记忆状态，而在每次执行的时候，游戏P2会对整个状态空间进行DFS搜索，其本质就是对博弈树进行DFS枚举搜索。

我们来看一下具体的一个对弈过程。我们用索引0-8代表棋盘上的9个位置。

假设： 玩家 X 采取最优开局，落子在中央（索引 4）。

0 1 2
_ _ _
_ X _
_ _ _

当前棋盘状态 (Level 1): [_, _, _, _, X, _, _, _, _]轮到 P2 (O) 决策 (MAX 层)

Level 1：P2 (O) 决策 (MAX 动作)

P2 遍历所有 8 个空位，尝试落子 O。这是 P2 的 MAXIMIZING 动作，目标是 \(\max(+1, 0, -1)\)。

\[ \text{Score} = \max \big\{ \text{Minimax}(\text{O 走 0}), \text{Minimax}(\text{O 走 1}), \dots, \text{Minimax}(\text{O 走 8}) \big\} \]

其对应状态如下：

P2 (O) 动作 产生的子状态 进入下一层
O 走 0 [O, _, _, _, X, _, _, _, _] \(\to\)Level 2 (MIN)
O 走 1 [_, O, _, _, X, _, _, _, _] \(\to\)Level 2 (MIN)
O 走 2 [_, _, O, _, X, _, _, _, _] \(\to\)Level 2 (MIN)
\(\dots\) \(\dots\) \(\dots\)

Level 2：P1 (X) 预测 (MIN 动作)

Minimax 算法递归到这一层，预测对手 X 会采取最小化 P2 收益的动作。这是 MINIMIZING 动作，目标是 \(\min(+1, 0, -1)\)。

假设 P2 选择了 O 走 0 ：[O, _, _, _, X, _, _, _, _]

P1 (X) 现在有 7 个空位可以落子。Minimax 遍历这 7 个动作：

\[ \text{Minimax}(\text{O 走 0}) = \min \big\{ \text{Minimax}(\text{X 走 1}), \dots, \text{Minimax}(\text{X 走 8}) \big\} \]

状态如下：

P1 (X) 预测动作 产生的子状态 进入下一层
X 走 1 [O, X, _, _, X, _, _, _, _] \(\to\)Level 3 (MAX)
X 走 2 [O, _, X, _, X, _, _, _, _] \(\to\)Level 3 (MAX)
\(\dots\) \(\dots\) \(\dots\)

Level 3：P2 (O) 再次决策 (MAX 动作)

Minimax 算法递归到这一层，P2 会尝试采取最大化收益的动作。P2 此时有 6 个空位可以落子。

\[ \text{Minimax}(\text{X 走 1}) = \max \big\{ \text{Minimax}(\text{O 走 2}), \dots, \text{Minimax}(\text{O 走 8}) \big\} \]

这个过程会一直重复，直到搜索到叶节点（胜利、失败、平局），然后将 \(\mathbf{+1, 0, -1}\) 的估值逐层回溯，最终确定 Level 1 的最佳动作。

简单来说，P2第一次DFS搜索时，搜索到Level8会看到一个满的棋盘，这个时候+1、0还是-1是确定的。整个搜索过程中的状态和对应的结果都会被记录，并取最大保证价值（因为P2默认两人都会按照最大化自己利益的原则去走）。一般到第二次、第三次搜索，因为memo已经存储了状态和最大价值结果，P2可以更快判断最终估值并给出最优选择。

memo记忆的值可靠的核心原因在于：

  • 任何一个棋盘状态，其minimax的估值都是唯一的，因此memo记录的就是最优子树的最终估值
  • 第一次搜索在当前分支一定会搜索到一个终局状态（base case），从而保证结果的准确性

正是这种机制，让Minimax 算法能够将计算次数从指数级的 25 万条路径 ，优化到多项式级的 5478 个独特状态 。

任何零和游戏，理论上都能啊按照上述方法得到一张记载着每个状态确切的价值的memo表，无论是国际象棋、中国象棋、还是围棋，本质上都是minimax博弈。这就是齐美洛定理 (Zermelo's Theorem)：

如果双方都采取最优策略，国际象棋的初始状态必然具有一个确定的结果：白方（先手）必胜、黑方（后手）必胜，或双方必平。

然而，国际象棋的状态总数约 \(10^{43}\) 到 \(10^{50}\)，围棋的状态总数约 \(10^{170}\)，而现代超级计算机能暴力解决（即完全计算并存储 Minimax 估值）的minimax博弈状态数量极限大约是\(10^{14}\)。国际象棋的状态总数之所以不是一个确切值，是因为国际象棋中可能会出现循环结局从而导致无限循环，因此国际象棋制定了三次重复局面和五十步规则的平局规则。对国际象棋博弈树复杂度的估算中，最有名的是香农在1950年的论文《Programming a Computer for Playing Chess》中给出的，也被称为香农数（Shannon Number）。

关于Minimax以及更深入的部分，请参考笔记：古典人工智能>>对抗搜索和博弈，在那篇笔记中我系统性地整理了从minimax到国际象棋和围棋（AlphaGo）的策略和实现等。

评论 #