动态规划

动态规划思想

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

如果一个问题的最优解包含其子问题的 最优解 ，那么这个问题就具有最优子结构（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（自顶向下）

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

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

Tabulation（自底向上）

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

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

解题步骤

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

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]\) 依赖于序列中靠前的元素。

斐波那契数列

斐波那契数列（Fibonacci Sequence）是最经典的DP入门问题。给定 \(n\)，求第 \(n\) 个斐波那契数。

状态定义： \(dp[i]\) 表示第 \(i\) 个斐波那契数。

Base Case：

\[ dp[0] = 0, \quad dp[1] = 1 \]

状态转移方程：

\[ dp[i] = dp[i-1] + dp[i-2], \quad i \geq 2 \]

时间复杂度： \(O(n)\)，空间复杂度： \(O(1)\)（滚动变量优化后）

def fib(n: int) -> int:
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

朴素递归的时间复杂度为 \(O(2^n)\)，因为存在大量重叠子问题。使用DP（Tabulation或Memoization）可以将时间复杂度降到 \(O(n)\)。这正是动态规划思想的最佳体现：通过存储子问题的解来消除重复计算。

最长递增子序列（LIS）

最长递增子序列（Longest Increasing Subsequence）：给定一个整数数组 \(nums\)，找到其中最长的严格递增子序列的长度。注意子序列不要求连续，但要求相对顺序不变。

状态定义： \(dp[i]\) 表示以 \(nums[i]\) 结尾的最长递增子序列的长度。

Base Case：

\[ dp[i] = 1, \quad \forall \, i \in [0, n-1] \]

每个元素本身构成长度为 1 的子序列。

状态转移方程：

\[ dp[i] = \max_{0 \leq j < i, \, nums[j] < nums[i]} \left( dp[j] + 1 \right) \]

最终答案为 \(\max(dp[0], dp[1], \ldots, dp[n-1])\)。

时间复杂度： \(O(n^2)\)，空间复杂度： \(O(n)\)

def lis_dp(nums: list[int]) -> int:
    n = len(nums)
    if n == 0:
        return 0
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

\(O(n \log n)\) 的贪心 + 二分查找优化： 维护一个数组 \(tails\)，其中 \(tails[i]\) 表示长度为 \(i+1\) 的递增子序列的最小末尾元素。遍历 \(nums\) 中的每个元素，用二分查找在 \(tails\) 中找到第一个 \(\geq\) 当前元素的位置并替换，若不存在则追加到末尾。

import bisect

def lis_bisect(nums: list[int]) -> int:
    tails = []
    for x in nums:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

贪心策略的直觉：为了让递增子序列尽可能长，我们希望每个长度的子序列的末尾元素尽可能小，这样后续元素才更容易接上去。

Kadane's最大子数组和

最大子数组和（Maximum Subarray Sum）：给定一个整数数组 \(nums\)，找到一个具有最大和的连续子数组（至少包含一个元素），返回其最大和。这就是经典的Kadane's Algorithm。

状态定义： \(dp[i]\) 表示以 \(nums[i]\) 结尾的连续子数组的最大和。

Base Case：

\[ dp[0] = nums[0] \]

状态转移方程：

\[ dp[i] = \max\left( nums[i], \quad dp[i-1] + nums[i] \right) \]

核心思想：对于每个位置 \(i\)，要么将当前元素接到前面的子数组后面（\(dp[i-1] + nums[i]\)），要么从当前元素重新开始（\(nums[i]\)）。如果前面的累积和已经是负数，那就不如从当前元素重新开始。

最终答案为 \(\max(dp[0], dp[1], \ldots, dp[n-1])\)。

时间复杂度： \(O(n)\)，空间复杂度： \(O(1)\)（只需一个变量记录前一个状态）

def max_subarray(nums: list[int]) -> int:
    max_sum = curr_sum = nums[0]
    for i in range(1, len(nums)):
        curr_sum = max(nums[i], curr_sum + nums[i])
        max_sum = max(max_sum, curr_sum)
    return max_sum

最大乘积子数组

最大乘积子数组（Maximum Product Subarray）：给定一个整数数组 \(nums\)，找到一个具有最大乘积的连续子数组，返回其最大乘积。

本题与最大子数组和不同的地方在于：负数乘以负数会变成正数，因此我们需要同时跟踪当前位置结尾的最大乘积和最小乘积。

状态定义：

• \(dp\_max[i]\) 表示以 \(nums[i]\) 结尾的连续子数组的最大乘积
• \(dp\_min[i]\) 表示以 \(nums[i]\) 结尾的连续子数组的最小乘积

Base Case：

\[ dp\_max[0] = dp\_min[0] = nums[0] \]

状态转移方程：

\[ dp\_max[i] = \max\left( nums[i], \quad dp\_max[i-1] \times nums[i], \quad dp\_min[i-1] \times nums[i] \right) \]

\[ dp\_min[i] = \min\left( nums[i], \quad dp\_max[i-1] \times nums[i], \quad dp\_min[i-1] \times nums[i] \right) \]

当 \(nums[i]\) 为负数时，前一步的最小乘积乘以负数可能变成最大乘积，这就是需要同时跟踪最大和最小的原因。

时间复杂度： \(O(n)\)，空间复杂度： \(O(1)\)

def max_product(nums: list[int]) -> int:
    result = cur_max = cur_min = nums[0]
    for i in range(1, len(nums)):
        candidates = (nums[i], cur_max * nums[i], cur_min * nums[i])
        cur_max, cur_min = max(candidates), min(candidates)
        result = max(result, cur_max)
    return result

打家劫舍

打家劫舍（House Robber）：一个小偷计划沿着一条街偷窃，每栋房子里有一定金额的现金。约束条件是不能偷相邻的两栋房子（否则会触发报警），问最多能偷到多少钱。

状态定义： \(dp[i]\) 表示偷到第 \(i\) 栋房子时能获得的最大金额。

Base Case：

\[ dp[0] = nums[0], \quad dp[1] = \max(nums[0], nums[1]) \]

状态转移方程：

\[ dp[i] = \max\left( dp[i-1], \quad dp[i-2] + nums[i] \right) \]

对于第 \(i\) 栋房子，有两种选择：不偷第 \(i\) 栋（收益为 \(dp[i-1]\)），或者偷第 \(i\) 栋（收益为 \(dp[i-2] + nums[i]\)，因为不能偷相邻的，所以要从 \(i-2\) 转移）。

时间复杂度： \(O(n)\)，空间复杂度： \(O(1)\)（滚动变量优化后）

def rob(nums: list[int]) -> int:
    if len(nums) <= 2:
        return max(nums)
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
    return prev1

Two-Sequence DP

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

最长公共子序列（LCS）

最长公共子序列（Longest Common Subsequence）：给定两个字符串 \(X\) 和 \(Y\)，找到它们的最长公共子序列的长度。子序列不要求连续，但要求保持相对顺序。

状态定义： \(dp[i][j]\) 表示 \(X\) 的前 \(i\) 个字符和 \(Y\) 的前 \(j\) 个字符的最长公共子序列长度。

Base Case：

\[ dp[i][0] = 0, \quad dp[0][j] = 0 \]

任一字符串为空时，LCS长度为0。

状态转移方程：

\[ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } X[i-1] = Y[j-1] \\ \max\left( dp[i-1][j], \quad dp[i][j-1] \right) & \text{if } X[i-1] \neq Y[j-1] \end{cases} \]

如果两个字符相等，就在左上角的状态基础上加1；否则取上方或左方的较大值。

时间复杂度： \(O(mn)\)，空间复杂度： \(O(mn)\)（可优化至 \(O(\min(m, n))\)）

def lcs(X: str, Y: str) -> int:
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

Edit Distance

编辑距离（Edit Distance / Levenshtein Distance）：给定两个字符串 \(word1\) 和 \(word2\)，求将 \(word1\) 转换为 \(word2\) 所需的最少操作次数。允许的操作有三种：插入（Insert）、删除（Delete）、替换（Replace）一个字符。

状态定义： \(dp[i][j]\) 表示将 \(word1\) 的前 \(i\) 个字符转换为 \(word2\) 的前 \(j\) 个字符所需的最少操作次数。

Base Case：

\[ dp[i][0] = i, \quad dp[0][j] = j \]

将一个非空字符串转换为空串需要全部删除，将空串转换为非空字符串需要全部插入。

状态转移方程：

\[ dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } word1[i-1] = word2[j-1] \\ 1 + \min \begin{cases} dp[i-1][j] & \text{（删除）} \\ dp[i][j-1] & \text{（插入）} \\ dp[i-1][j-1] & \text{（替换）} \end{cases} & \text{otherwise} \end{cases} \]

三种操作的含义：

• \(dp[i-1][j] + 1\)：删除 \(word1[i-1]\)，然后将 \(word1\) 前 \(i-1\) 个字符转换为 \(word2\) 前 \(j\) 个字符
• \(dp[i][j-1] + 1\)：先将 \(word1\) 前 \(i\) 个字符转换为 \(word2\) 前 \(j-1\) 个字符，然后插入 \(word2[j-1]\)
• \(dp[i-1][j-1] + 1\)：将 \(word1[i-1]\) 替换为 \(word2[j-1]\)

时间复杂度： \(O(mn)\)，空间复杂度： \(O(mn)\)

def edit_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

Edit Distance在自然语言处理（NLP）中有广泛的应用，例如拼写纠错、DNA序列比对等。

Interval DP

区间DP（Interval DP）：这类问题在一个区间 \([i, j]\) 上定义状态，通过枚举分割点或缩小区间来进行状态转移。计算顺序通常按区间长度从小到大进行。

最长回文子序列

最长回文子序列（Longest Palindromic Subsequence）：给定一个字符串 \(s\)，找到其中最长的回文子序列的长度。子序列不要求连续。

状态定义： \(dp[i][j]\) 表示字符串 \(s[i..j]\)（从索引 \(i\) 到 \(j\) 的子串）中最长回文子序列的长度。

Base Case：

\[ dp[i][i] = 1 \quad (\text{单个字符本身就是回文}) \]

状态转移方程：

\[ dp[i][j] = \begin{cases} dp[i+1][j-1] + 2 & \text{if } s[i] = s[j] \\ \max\left( dp[i+1][j], \quad dp[i][j-1] \right) & \text{if } s[i] \neq s[j] \end{cases} \]

如果两端字符相等，则它们可以加入回文子序列中；否则分别尝试去掉左端或右端取较大值。

计算顺序： 由于 \(dp[i][j]\) 依赖于 \(dp[i+1][...]\)，因此 \(i\) 必须从大到小遍历（或按区间长度从小到大遍历）。

时间复杂度： \(O(n^2)\)，空间复杂度： \(O(n^2)\)

def longest_palindrome_subseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for length in range(2, n + 1):      # 区间长度
        for i in range(n - length + 1):  # 起始索引
            j = i + length - 1           # 结束索引
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

另一种解法是将 \(s\) 反转得到 \(s'\)，然后求 \(s\) 和 \(s'\) 的LCS，其结果与最长回文子序列等价。

最长回文子串（LPS）

最长回文子串（Longest Palindromic Substring）：给定一个字符串 \(s\)，找到其中最长的连续回文子串。注意与最长回文子序列不同，这里要求子串必须是连续的。

状态定义： \(dp[i][j]\) 为布尔值，表示 \(s[i..j]\) 是否为回文串。

Base Case：

\[ dp[i][i] = \text{True} \quad (\text{单个字符}) \]

\[ dp[i][i+1] = (s[i] = s[i+1]) \quad (\text{两个字符}) \]

状态转移方程：

\[ dp[i][j] = \left( s[i] = s[j] \right) \wedge dp[i+1][j-1], \quad j - i \geq 2 \]

即：如果两端字符相等，且去掉两端后的子串也是回文，那么 \(s[i..j]\) 就是回文。在遍历过程中记录最长的回文子串即可。

时间复杂度： \(O(n^2)\)，空间复杂度： \(O(n^2)\)

def longest_palindrome_substr(s: str) -> str:
    n = len(s)
    if n < 2:
        return s
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1
    for i in range(n):
        dp[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = (length == 2) or dp[i + 1][j - 1]
            if dp[i][j] and length > max_len:
                start, max_len = i, length
    return s[start:start + max_len]

更高效的解法是 Manacher算法，可以在 \(O(n)\) 时间内找到最长回文子串。Manacher算法利用了回文的对称性，通过维护一个"回文半径数组"来避免重复比较。另外，中心扩展法 也是一种常用的 \(O(n^2)\) 时间、\(O(1)\) 空间的解法，从每个字符（或每对相邻字符）向两侧扩展来寻找回文。

RNA Folding

RNA二级结构预测（RNA Secondary Structure Prediction）：给定一条RNA序列 \(s = b_1 b_2 \ldots b_n\)，其中每个 \(b_i \in \{A, U, G, C\}\)，求最大碱基配对数。RNA中的合法配对为 A-U 和 G-C（Watson-Crick配对）。配对规则如下：

• 每个碱基最多参与一个配对
• 配对不能交叉（即如果 \((i, j)\) 和 \((k, l)\) 都是配对，且 \(i < k\)，则要么 \(j < k\)，要么 \(l < j\)）
• 配对的两个碱基之间至少间隔4个位置（\(j - i > 4\)），以保证物理上可以弯折

这是一个经典的区间DP问题。

状态定义： \(dp[i][j]\) 表示子序列 \(b_i, b_{i+1}, \ldots, b_j\) 中的最大配对数。

Base Case：

\[ dp[i][j] = 0, \quad \text{if } j - i \leq 4 \]

间隔不足4的子序列无法形成配对。

状态转移方程：

对于区间 \([i, j]\)，考虑碱基 \(b_j\) 的所有可能：

\[ dp[i][j] = \max \begin{cases} dp[i][j-1] & \text{（$b_j$ 不参与配对）} \\ \max_{i \leq t < j-4, \, \text{match}(t, j)} \left( 1 + dp[i][t-1] + dp[t+1][j-1] \right) & \text{（$b_j$ 与 $b_t$ 配对）} \end{cases} \]

其中 \(\text{match}(t, j)\) 表示 \(b_t\) 和 \(b_j\) 是合法的碱基配对。当 \(b_j\) 与 \(b_t\) 配对时，区间被分割为两个独立的子区间 \([i, t-1]\) 和 \([t+1, j-1]\)，这正是区间DP的核心思想。

时间复杂度： \(O(n^3)\)，空间复杂度： \(O(n^2)\)

def rna_folding(s: str) -> int:
    n = len(s)
    pair = {('A','U'), ('U','A'), ('G','C'), ('C','G')}
    dp = [[0] * n for _ in range(n)]
    for length in range(5, n):               # 区间长度至少为5
        for i in range(n - length):
            j = i + length
            # b_j 不配对
            dp[i][j] = dp[i][j - 1]
            # b_j 与某个 b_t 配对
            for t in range(i, j - 4):
                if (s[t], s[j]) in pair:
                    val = 1 + (dp[i][t - 1] if t > i else 0) + dp[t + 1][j - 1]
                    dp[i][j] = max(dp[i][j], val)
    return dp[0][n - 1]

RNA Folding是计算生物学中的重要问题，Nussinov算法就是基于上述区间DP的经典算法。实际应用中还会考虑自由能最小化等更复杂的评分模型。

矩阵链乘法

矩阵链乘法（Matrix Chain Multiplication）：给定 \(n\) 个矩阵的链 \(A_1, A_2, \ldots, A_n\)，其中矩阵 \(A_i\) 的维度为 \(p_{i-1} \times p_i\)，求计算它们乘积 \(A_1 A_2 \cdots A_n\) 时的最小标量乘法次数。矩阵乘法满足结合律，不同的加括号方式会导致不同的计算量。

例如三个矩阵 \(A_{10\times30}\)、\(B_{30\times5}\)、\(C_{5\times60}\)：

• \((AB)C\)：\(10\times30\times5 + 10\times5\times60 = 4500\) 次
• \(A(BC)\)：\(30\times5\times60 + 10\times30\times60 = 27000\) 次

加括号方式的不同导致了6倍的差异。

状态定义： \(dp[i][j]\) 表示计算矩阵链 \(A_i A_{i+1} \cdots A_j\) 所需的最小标量乘法次数。

Base Case：

\[ dp[i][i] = 0 \quad (\text{单个矩阵无需乘法}) \]

状态转移方程：

\[ dp[i][j] = \min_{i \leq k < j} \left( dp[i][k] + dp[k+1][j] + p_{i-1} \cdot p_k \cdot p_j \right) \]

枚举分割点 \(k\)，将矩阵链分为 \(A_i \cdots A_k\) 和 \(A_{k+1} \cdots A_j\) 两部分，两部分各自的最小计算量加上合并的代价 \(p_{i-1} \cdot p_k \cdot p_j\)。

计算顺序： 按区间长度从小到大遍历。

时间复杂度： \(O(n^3)\)，空间复杂度： \(O(n^2)\)

def matrix_chain_order(p: list[int]) -> int:
    """p: 维度数组，长度 n+1，矩阵 A_i 的维度为 p[i-1] x p[i]"""
    n = len(p) - 1
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):       # 链长度
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n - 1]

Knapsack DP

背包DP（Knapsack DP）：这类问题的核心是在有限的容量约束下，选择物品使得总价值最大化（或满足某种最优条件）。根据物品的选取规则，可以分为0/1背包、完全背包和多重背包等变体。

0/1背包问题

0/1背包问题（0/1 Knapsack Problem）：有 \(n\) 个物品，每个物品有重量 \(w_i\) 和价值 \(v_i\)，背包容量为 \(W\)。每个物品只能选择放入或不放入（不能拆分），求在不超过背包容量的前提下，能装入的最大总价值。

状态定义： \(dp[i][j]\) 表示从前 \(i\) 个物品中选择、背包容量为 \(j\) 时的最大价值。

Base Case：

\[ dp[0][j] = 0, \quad dp[i][0] = 0 \]

没有物品可选或背包容量为0时，最大价值为0。

状态转移方程：

\[ dp[i][j] = \begin{cases} dp[i-1][j] & \text{if } w_i > j \quad \text{（装不下第 $i$ 个物品）} \\ \max\left( dp[i-1][j], \quad dp[i-1][j-w_i] + v_i \right) & \text{if } w_i \leq j \end{cases} \]

对于每个物品，要么不选（继承 \(dp[i-1][j]\)），要么选（从剩余容量 \(j - w_i\) 的状态转移并加上当前物品价值）。

时间复杂度： \(O(nW)\)，空间复杂度： \(O(nW)\)（可用滚动数组优化至 \(O(W)\)）

def knapsack_01(weights: list[int], values: list[int], W: int) -> int:
    n = len(weights)
    # 空间优化：一维DP，从后向前遍历防止重复使用同一物品
    dp = [0] * (W + 1)
    for i in range(n):
        for j in range(W, weights[i] - 1, -1):  # 逆序遍历
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[W]

空间优化的关键在于逆序遍历容量：由于 \(dp[i][j]\) 只依赖于 \(dp[i-1][...]\)，即上一行的数据，逆序遍历可以保证在更新 \(dp[j]\) 时，\(dp[j - w_i]\) 还是上一轮（即 \(i-1\) 轮）的值，从而保证每个物品最多只被选一次。

Coin Changing

硬币找零（Coin Change）：给定不同面额的硬币 \(coins = [c_1, c_2, \ldots, c_m]\) 和一个总金额 \(amount\)，求凑成总金额所需的最少硬币个数。每种硬币可以使用无限次。如果无法凑成，返回 \(-1\)。

状态定义： \(dp[j]\) 表示凑成金额 \(j\) 所需的最少硬币数。

Base Case：

\[ dp[0] = 0 \quad (\text{凑成金额 0 不需要硬币}) \]

\[ dp[j] = \infty, \quad j \geq 1 \quad (\text{初始化为无穷大，表示暂时无法凑成}) \]

状态转移方程：

\[ dp[j] = \min_{c \in coins, \, c \leq j} \left( dp[j - c] + 1 \right) \]

对每个金额 \(j\)，尝试使用每种硬币 \(c\)，取所有合法选择中的最小值。

时间复杂度： \(O(amount \times m)\)，空间复杂度： \(O(amount)\)

def coin_change(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for j in range(1, amount + 1):
        for c in coins:
            if c <= j:
                dp[j] = min(dp[j], dp[j - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

注意Coin Change与完全背包的关系：Coin Change本质上就是一个完全背包问题的变体，只不过优化目标从"最大价值"变成了"最少物品数"。

完全背包

完全背包问题（Unbounded Knapsack）：与0/1背包问题类似，有 \(n\) 种物品，每种物品有重量 \(w_i\) 和价值 \(v_i\)，背包容量为 \(W\)。区别在于每种物品可以选取无限次，求最大总价值。

状态定义： \(dp[j]\) 表示背包容量为 \(j\) 时的最大价值。

Base Case：

\[ dp[0] = 0 \]

状态转移方程：

\[ dp[j] = \max_{w_i \leq j} \left( dp[j - w_i] + v_i \right) \]

与0/1背包的关键区别： 遍历容量时使用正序而非逆序。正序遍历意味着在同一轮中 \(dp[j - w_i]\) 可能已经包含了第 \(i\) 种物品，从而实现了"每种物品可以无限次选取"的效果。

时间复杂度： \(O(nW)\)，空间复杂度： \(O(W)\)

def unbounded_knapsack(weights: list[int], values: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for j in range(weights[i], W + 1):  # 正序遍历
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[W]

背包类型	遍历容量顺序	原因
0/1背包	逆序（从 \(W\) 到 \(w_i\)）	保证每个物品最多使用一次
完全背包	正序（从 \(w_i\) 到 \(W\)）	允许每个物品使用多次

多重背包

多重背包问题（Bounded Knapsack）：有 \(n\) 种物品，第 \(i\) 种物品有重量 \(w_i\)、价值 \(v_i\)、数量上限 \(c_i\)。背包容量为 \(W\)，求最大总价值。

朴素做法是将第 \(i\) 种物品展开为 \(c_i\) 个独立物品，然后按0/1背包求解，但时间复杂度为 \(O(W \sum c_i)\)，当数量较大时效率很低。

二进制优化： 将每种物品的数量 \(c_i\) 拆分为若干"捆"，每捆的数量为 \(1, 2, 4, 8, \ldots\)（二进制拆分），使得这些捆的任意子集之和可以表示 \(0\) 到 \(c_i\) 之间的任意整数。例如 \(c_i = 13\) 拆分为 \(1, 2, 4, 6\)（最后一个为余数 \(13 - 1 - 2 - 4 = 6\)）。拆分后每"捆"作为一个独立的0/1背包物品。

这样物品总数从 \(\sum c_i\) 降低到 \(\sum \log c_i\)，时间复杂度变为 \(O(W \sum \log c_i)\)。

状态转移方程： 拆分后按0/1背包处理：

\[ dp[j] = \max\left( dp[j], \quad dp[j - w'] + v' \right) \]

其中 \(w'\) 和 \(v'\) 是拆分后每"捆"的重量和价值。

时间复杂度： \(O(nW\log c_{max})\)，空间复杂度： \(O(W)\)

def bounded_knapsack(weights, values, counts, W):
    # 二进制拆分
    new_w, new_v = [], []
    for i in range(len(weights)):
        c = counts[i]
        k = 1
        while k <= c:
            new_w.append(weights[i] * k)
            new_v.append(values[i] * k)
            c -= k
            k *= 2
        if c > 0:
            new_w.append(weights[i] * c)
            new_v.append(values[i] * c)
    # 转化为 0/1 背包
    dp = [0] * (W + 1)
    for i in range(len(new_w)):
        for j in range(W, new_w[i] - 1, -1):  # 逆序
            dp[j] = max(dp[j], dp[j - new_w[i]] + new_v[i])
    return dp[W]

背包类型	每种物品数量	时间复杂度
0/1背包	1	\(O(nW)\)
完全背包	无限	\(O(nW)\)
多重背包	\(c_i\)	\(O(nW\log c_{max})\)（二进制优化）

2D-DP

二维DP（2D-DP）：这类问题通常在二维网格上进行操作，状态 \(dp[i][j]\) 表示到达网格位置 \((i, j)\) 时的某种最优值或方案数。

Unique Paths

不同路径（Unique Paths）：一个机器人位于 \(m \times n\) 网格的左上角，每次只能向下或向右移动一步，问到达右下角共有多少条不同的路径。

状态定义： \(dp[i][j]\) 表示从左上角到达位置 \((i, j)\) 的不同路径数。

Base Case：

\[ dp[i][0] = 1, \quad dp[0][j] = 1 \]

第一行和第一列的每个位置都只有一条路径可以到达（一直向右或一直向下）。

状态转移方程：

\[ dp[i][j] = dp[i-1][j] + dp[i][j-1] \]

到达 \((i, j)\) 只能从上方 \((i-1, j)\) 或左方 \((i, j-1)\) 而来。

时间复杂度： \(O(mn)\)，空间复杂度： \(O(n)\)（按行滚动）

def unique_paths(m: int, n: int) -> int:
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    return dp[n - 1]

本题也可以用组合数学直接求解：从左上到右下一共走 \(m + n - 2\) 步，其中 \(m - 1\) 步向下、\(n - 1\) 步向右，因此答案为 \(\binom{m+n-2}{m-1}\)。

三角形最小路径和

三角形最小路径和（Triangle Minimum Path Sum）：给定一个三角形（用二维列表表示），从顶部到底部找一条路径，使得路径上的数字之和最小。每一步只能移动到下一行的相邻节点（即位置 \((i, j)\) 只能移动到 \((i+1, j)\) 或 \((i+1, j+1)\)）。

状态定义： \(dp[i][j]\) 表示从顶部到达位置 \((i, j)\) 的最小路径和。

Base Case：

\[ dp[0][0] = triangle[0][0] \]

状态转移方程：

\[ dp[i][j] = triangle[i][j] + \begin{cases} dp[i-1][0] & \text{if } j = 0 \\ dp[i-1][j-1] & \text{if } j = i \\ \min\left( dp[i-1][j-1], \quad dp[i-1][j] \right) & \text{otherwise} \end{cases} \]

最终答案为最后一行的最小值：\(\min(dp[n-1][0], dp[n-1][1], \ldots, dp[n-1][n-1])\)。

时间复杂度： \(O(n^2)\)，空间复杂度： \(O(n)\)（可以自底向上DP，直接在一维数组上操作）

自底向上的方法更简洁：从最后一行开始，逐行向上合并，最终 \(dp[0]\) 就是答案。

def minimum_total(triangle: list[list[int]]) -> int:
    dp = triangle[-1][:]  # 从最后一行开始
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(len(triangle[i])):
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
    return dp[0]

Tree DP

树形DP（Tree DP）是在树结构上进行的动态规划。状态定义在树的节点上，转移方向通常是从子节点到父节点（自底向上）。由于树没有环，天然具有最优子结构和无后效性，非常适合DP。

经典例题：树的最大独立集（Maximum Independent Set on Tree）

给定一棵有 \(n\) 个节点的树，每个节点有一个权重 \(w_i\)。选择若干节点使得被选中的节点中没有任何两个相邻（有边直接相连），求被选节点的最大权重和。

状态定义：

• \(dp[u][0]\)：不选节点 \(u\) 时，以 \(u\) 为根的子树的最大权重和
• \(dp[u][1]\)：选节点 \(u\) 时，以 \(u\) 为根的子树的最大权重和

状态转移方程：

\[ dp[u][0] = \sum_{v \in \text{children}(u)} \max\left( dp[v][0], \, dp[v][1] \right) \]

\[ dp[u][1] = w_u + \sum_{v \in \text{children}(u)} dp[v][0] \]

不选 \(u\) 时，子节点可选可不选；选 \(u\) 时，子节点都不能选。

时间复杂度： \(O(n)\)，每个节点只访问一次。

def max_independent_set(adj, weights, root=0):
    n = len(weights)
    dp = [[0, 0] for _ in range(n)]
    visited = [False] * n

    def dfs(u):
        visited[u] = True
        dp[u][1] = weights[u]
        for v in adj[u]:
            if not visited[v]:
                dfs(v)
                dp[u][0] += max(dp[v][0], dp[v][1])
                dp[u][1] += dp[v][0]

    dfs(root)
    return max(dp[root][0], dp[root][1])

Bitmask DP

状态压缩DP（Bitmask DP）使用二进制位来表示集合的状态。一个 \(n\) 位的整数可以表示一个大小为 \(n\) 的集合中每个元素是否被选中（1表示选中，0表示未选中），总共有 \(2^n\) 种状态。适用于 \(n\) 较小（通常 \(n \leq 20\)）的情况。

经典例题：旅行商问题（TSP, Travelling Salesman Problem）

给定 \(n\) 个城市和任意两个城市之间的距离 \(dist[i][j]\)，求从城市 0 出发、经过每个城市恰好一次并回到城市 0 的最短路径长度。

状态定义： \(dp[S][i]\) 表示已经访问过的城市集合为 \(S\)（用bitmask表示），且当前所在城市为 \(i\) 时的最短路径长度。

Base Case：

\[ dp[\{0\}][0] = 0 \quad \text{即 } dp[1][0] = 0 \]

从城市 0 出发，只访问过城市 0，路径长度为 0。

状态转移方程：

\[ dp[S][i] = \min_{j \in S, \, j \neq i, \, \text{bit } i \in S} \left( dp[S \setminus \{i\}][j] + dist[j][i] \right) \]

从状态 \(S\) 中去掉城市 \(i\) 后，枚举上一个访问的城市 \(j\)。

最终答案为：

\[ \min_{i=1}^{n-1} \left( dp[2^n - 1][i] + dist[i][0] \right) \]

时间复杂度： \(O(2^n \cdot n^2)\)，空间复杂度： \(O(2^n \cdot n)\)

def tsp(dist: list[list[int]]) -> int:
    n = len(dist)
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 起点为城市0，bitmask = ...0001

    for S in range(1, 1 << n):
        for i in range(n):
            if not (S >> i & 1) or dp[S][i] == INF:
                continue
            for j in range(n):
                if S >> j & 1:
                    continue  # j 已经访问过
                dp[S | (1 << j)][j] = min(dp[S | (1 << j)][j],
                                          dp[S][i] + dist[i][j])

    full = (1 << n) - 1
    return min(dp[full][i] + dist[i][0] for i in range(1, n))

TSP是NP-hard问题，暴力枚举所有排列的复杂度为 \(O(n!)\)，使用Bitmask DP可以优化到 \(O(2^n \cdot n^2)\)，在 \(n \leq 20\) 时是可行的。

Digital DP

数位DP（Digital DP）用于解决与数字的各个数位（digit）相关的计数问题。典型问题形式是：在区间 \([L, R]\) 内，满足某种数位性质的数有多少个。例如："在 \([1, N]\) 中，各数位之和为 \(S\) 的数有多少个"、"不包含数字4的数有多少个"等。

核心思想： 逐位构造数字，使用一个 tight 标志位来表示当前是否还受到上界 \(N\) 的约束。如果前面所有位都取到了 \(N\) 对应位的上界值，则当前位最多只能取到 \(N\) 对应位的值（tight = True）；否则当前位可以取 \(0\) 到 \(9\)（tight = False）。

状态定义： \(dp[pos][state][tight]\)，其中 \(pos\) 是当前处理到第几位，\(state\) 是与具体问题相关的状态（如数位之和、是否出现某个数字等），\(tight\) 表示是否受上界约束。

通用模板（记忆化搜索）：

from functools import lru_cache

def count(N: int) -> int:
    """计算 [0, N] 中满足条件的数的个数"""
    digits = list(map(int, str(N)))

    @lru_cache(maxsize=None)
    def dfs(pos, state, tight, started):
        if pos == len(digits):
            return 1 if started else 0  # 根据问题调整
        limit = digits[pos] if tight else 9
        result = 0
        for d in range(0, limit + 1):
            result += dfs(
                pos + 1,
                new_state(state, d),       # 根据问题定义状态转移
                tight and (d == limit),
                started or (d > 0)
            )
        return result

    return dfs(0, initial_state, True, False)

其中 \(started\) 标志用于处理前导零问题。对于区间 \([L, R]\) 的查询，可以转化为 \(count(R) - count(L - 1)\)，即前缀和思想。

数位DP的时间复杂度通常为 \(O(\log N \times |state| \times 10)\)，其中 \(|state|\) 是状态空间的大小，与具体问题相关。相比暴力枚举 \(O(N)\) 的做法，数位DP在 \(N\) 极大时（如 \(10^{18}\)）有着巨大的优势。

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）的策略和实现等。

---

评论