动态规划

解决动态规划（Dynamic Programming, DP）问题，就像是拼拼图：你不能直接看到全貌，但可以通过组合已经拼好的小板块来构建大图。

该问题特征识别: 状态转移方程, 最优子结构

DP四部曲

通常我们可以遵循“DP 四部曲”来攻克任何一道动规题：

确定 DP 数组及其下标的含义

这是最关键的一步。你需要明确 $dp[i]$ 到底代表什么？ 即怎么用数据模型描述

• 在“爬楼梯”中，$dp[i]$ 表示：到达第 $i$ 层台阶所花费的最小体力值。
• 如果不清楚含义，后面的递推公式就会逻辑混乱。

确定状态转移方程

也就是“找关系”。思考：要到达 $dp[i]$，前一步可能在哪里？

• 因为你每次只能走 1 步或 2 步，所以要到达第 $i$ 层，只能从第 $i-1$ 层或第 $i-2$ 层跨上来。
• 为了取最小花费，方程就是：

$$dp[i] = \min(dp[i-1], dp[i-2]) + cost[i]$$

初始化 DP 数组

DP 是靠推导出来的，所以必须有“第一块砖”。

• 根据题意，你可以从索引 0 或 1 开始，且不消耗体力。
• 初始化：$dp[0] = cost[0]$, $dp[1] = cost[1]$。
• 注意： 如果初始化错了，后面的结果会像多米诺骨牌一样全线崩塌。

确定遍历顺序

从前往后还是从后往前？

• 对于楼梯问题，由于 $dp[i]$ 依赖于 $dp[i-1]$ 和 $dp[i-2]$，所以必须从左到右遍历。

总结：从“记忆化”到“空间优化”

当你写出基础的代码后，可以尝试更高级的思考：

子问题拆解：DP 思维的核心突破口

解决"动态规划（DP）或递归问题中如何拆解子问题"是算法设计中最核心的思维突破口。

要掌握子问题的拆解，可以遵循一套标准的思考框架，并结合具体的拆解模式来训练直觉。

子问题拆解的"三步思考法"

在拆解子问题时，不要一上来就尝试写代码，而是依次回答以下 3 个核心问题：

寻找"最后一步"（Last Step）

假设原问题已经被解决，思考形成这个最终解的前一步发生了什么。

• 例（Scramble String）：假设 $s_1$ 和 $s_2$ 已经是 scramble 的，那它们最后一次分割在哪里？最后这一步要么"没交换左右两部分"，要么"交换了左右两部分"。
• 例（最长递增子序列 LIS）：假设最长子序列以数字 $x$ 结尾，那么 $x$ 的前一个数字是谁？

识别"变动状态"（Variables）

要描述任何一个子问题，需要哪些参数（维度）才能唯一确定它？

• 序列/字符串：通常由区间范围（$[i, j]$）、前缀/后缀（$i$ 或 $len$）来确定。
• 背包/约束条件：通常由剩余容量/剩余步数（$w$ 或 $k$）来确定。
• 规则：如果在 $s_1$ 和 $s_2$ 中各选一段子串，至少需要 3 个变量（$s_1$ 起点 $i$、$s_2$ 起点 $j$、子串长度 $k$）。

建立"无后效性"的边界与转移（Transition & State）

子问题的求解不能依赖后续更高级别的决策，只能依赖比它规模更小、已经解决完的子状态。

• 核心检验：缩小问题规模（长度 $N \to N-1$ 或 $k \to k-p$）后，问题结构是否保持完全一致？

常见的子问题拆解模式

绝大多数 DP 题目的拆解可以归纳为以下 4 种基本模式：

模式 1：前缀/后缀分解（从序列一端剥离）

每次决策只影响序列的开头或结尾。

• 适用场景：爬楼梯、打家劫舍（House Robber）、买卖股票、最长上升子序列（LIS）。
• 拆解逻辑：求解长度为 $n$ 的问题，可以归结为求解 $n-1$ 或 $n-2$ 的问题。

$$\text{Problem}(n) \to \text{Choose}(n) + \text{Problem}(n-1)$$

模式 2：双序列双指针分解

同时处理两个序列（如字符串、数组），通常看它们的结尾字符/元素。

• 适用场景：最长公共子序列（LCS）、编辑距离（Edit Distance）。
• 拆解逻辑：比较 $s_1[i]$ 和 $s_2[j]$ 是否相等：
  • 若相等：归结为 $(i-1, j-1)$ 的子问题。
  • 若不相等：归结为 $(i-1, j)$ 或 $(i, j-1)$ 的子问题。

模式 3：区间/分割点分解（从中间切开）

问题的解答取决于将一个大区间切分成若干小区间，或者从中间某个位置做出选择。

• 适用场景：Scramble String、矩阵链乘、戳气球（Burst Balloons）、石子合并。
• 拆解逻辑：在区间 $[i, j]$ 内枚举每一个可能的分割点 $k$（$i \le k < j$），将大问题拆为 $[i, k]$ 和 $[k+1, j]$ 两个完全独立的小问题。

$$\text{Problem}(i, j) = \min_{k} \Big( \text{Problem}(i, k) + \text{Problem}(k+1, j) + \text{Cost} \Big)$$

模式 4：状态维度叠加（状态机/约束扩展）

除了位置维度，还需要额外的维度来记录"当前的状态或选择限制"。

• 适用场景：带有冷却时间的股票交易、背包问题（限制容量）、网格到达（限制转向次数）。
• 拆解逻辑：dp[i][state] 表示到了第 $i$ 个位置，且处于 state 状态时的最优解。

实战演练：如何用"切分点思维"思考复杂题

以 87. Scramble String 为例，直觉拆解流程如下：

1. 原问题：$s_1[0\dots N-1]$ 和 $s_2[0\dots N-1]$ 是否 match？
2. 问自己"最后一步"：$s_1$ 肯定在某个位置 $p$ 被切成了左右两半。
3. 推导子问题：
   • 左半部分长度 $p$：$s_1[0 \dots p-1]$
   • 右半部分长度 $N-p$：$s_1[p \dots N-1]$
4. 问自己"对应关系"：$s_2$ 怎么切？
   • 不交换：$s_2[0 \dots p-1]$ 和 $s_2[p \dots N-1]$
   • 交换：$s_2[N-p \dots N-1]$ 和 $s_2[0 \dots N-p-1]$
5. 归纳子问题形式：发现子问题变成了："$s_1$ 中长为 $k$ 的某段子串" 与 “$s_2$ 中长为 $k$ 的某段子串” 是否匹配。
6. 参数化定义：确定状态需要 3 个参数：length（长度 $k$）、start1（$s_1$ 起点 $i$）、start2（$s_2$ 起点 $j$）。

避坑训练建议

1. 从自顶向下的递归（DFS + 记忆化）开始训练：不要一开始就强迫自己写自底向上的三维/四维循环。写 DFS 时，函数的参数（如 dfs(a, b)）就是子问题的定义，函数内部的 for 循环就是子问题的拆解逻辑。
2. 画递归树（Recursion Tree）：拿一个很短的输入（如 length = 3 或 4），在纸上画出递归调用的展开树，观察哪些分支的参数是一模一样的，这就是重叠子问题。
3. 先抽象参数，再找方程：如果觉得无从下手，先在纸上列出：描述当前状态最少需要几个变量？ 变量找准了，转移方程往往水到渠成。

DP 的通用本质与统一范式

动态规划的核心本质不是某种特定的“公式”，而是一种问题的求解框架与思想。虽然各种题目呈现的状态方程和遍历顺序千差万别，但底层都遵循着统一的决策范式。

统一的状态转移范式

所有的 DP 状态本质上都是在解答：

$$\text{DP}(\text{当前状态 } S) = \text{最优值}$$

其通用状态转移公式可表示为：

经典场景的映射关系如下：

统一的建模解题套路

遇到任何 DP 问题，都可以按以下三步拆解：

1. 定义“状态”（精简历史）： 用最少的信息描述当前局势，遵循无后效性原则（只关心现在处于什么状态，不关心是如何到达这里的）。
2. 穷举“决策”（列出分支）： 列出当前状态下的合法选择以及选择带来的收益与状态演进。
3. 确定“基底与拓扑序”（从小到大）： 明确已知的基础状态（Base Case），并确保计算某状态时其依赖的子状态已求解完成。

总结： 动态规划是用状态去压缩历史，用决策去连接未来，用记忆去消除重复计算。

经典 DP 模型与 LeetCode 题解

背包模型

0-1 背包：分割等和子集 (LeetCode 416)

• 题目要法：给定一个只包含正整数的非空数组 nums，判断是否能将数组分割成两个和相等的子集。
• 模型转换：等价于背包容量为 $W = \sum \text{nums} / 2$，从数组中选出若干数字，能否正好填满容量 $W$。
• 状态定义：$dp[j]$ 表示容量为 $j$ 的背包是否能被恰好填满（boolean）。
• 转移方程： $$dp[j] = dp[j] \lor dp[j - \text{num}]$$
• 代码实现 (空间优化版)：

func canPartition(nums []int) bool {
    totalSum := 0
    for _, num := range nums {
        totalSum += num
    }
    if totalSum%2 != 0 {
        return false
    }

    target := totalSum / 2
    dp := make([]bool, target+1)
    dp[0] = true // 容量为 0 时默认可填满

    for _, num := range nums {
        // 0-1背包倒序遍历容量，防止重复使用同一个物品
        for j := target; j >= num; j-- {
            dp[j] = dp[j] || dp[j-num]
        }
    }

    return dp[target]
}

完全背包：零钱兑换 (LeetCode 322)

• 题目要法：给定不同面额的硬币 coins 和总金额 amount，计算凑成总金额所需的最少硬币数（硬币数量无限）。
• 状态定义：$dp[i]$ 表示凑齐金额 $i$ 所需的最少硬币数。
• 转移方程： $$dp[i] = \min_{coin \in coins} (dp[i - coin] + 1)$$
• 代码实现：

func coinChange(coins []int, amount int) int {
    // dp[i] 初始化为 amount+1 表示不可达（相当于无穷大）
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1
    }
    dp[0] = 0 // 凑齐金额 0 需要 0 个硬币

    // 完全背包正序遍历容量，允许重复选取硬币
    for i := 1; i <= amount; i++ {
        for _, coin := range coins {
            if i-coin >= 0 && dp[i-coin]+1 < dp[i] {
                dp[i] = dp[i-coin] + 1
            }
        }
    }

    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

线性与子序列模型

最长递增子序列 LIS (LeetCode 300)

• 题目要法：给你一个整数数组 nums，找到其中最长严格递增子序列的长度。
• 状态定义：$dp[i]$ 表示以 nums[i] 结尾的最长严格递增子序列的长度。
• 转移方程： $$dp[i] = \max_{0 \le j < i, nums[j] < nums[i]} (dp[j] + 1)$$
• 代码实现：

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    dp := make([]int, len(nums))
    maxLen := 1

    for i := range nums {
        dp[i] = 1 // 每个元素自身都是一个长度为 1 的子序列
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] && dp[j]+1 > dp[i] {
                dp[i] = dp[j] + 1
            }
        }
        if dp[i] > maxLen {
            maxLen = dp[i]
        }
    }

    return maxLen
}

最长公共子序列 LCS (LeetCode 1143)

• 题目要法：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
• 状态定义：$dp[i][j]$ 表示 text1[0...i-1] 和 text2[0...j-1] 的最长公共子序列长度。
• 转移方程：

• 代码实现：

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                if dp[i-1][j] > dp[i][j-1] {
                    dp[i][j] = dp[i-1][j]
                } else {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }

    return dp[m][n]
}

最长公共子串 (Longest Common Substring)

子序列 vs 子串：

• 子序列 (Subsequence)：字符相对顺序不变，但不要求连续。
• 子串 (Substring)：字符必须严格连续。

• 题目要法：给定两个字符串 str1 和 str2，求它们最长的公共连续子串的长度。
• 状态定义：$dp[i][j]$ 表示以 str1[i-1] 和 str2[j-1] 结尾的最长公共子串的长度。
• 转移方程：

• 核心区别：一旦当前字符不相等，公共子串在这里断开，直接重置为 0，而最终结果是整个 $dp$ 数组中的最大值（全局变量维持）。
• 代码实现：

func longestCommonSubstring(str1 string, str2 string) int {
    m, n := len(str1), len(str2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    maxLen := 0
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if str1[i-1] == str2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > maxLen {
                    maxLen = dp[i][j]
                }
            } else {
                dp[i][j] = 0 // 不相等则断开，连续性中断，重置为 0
            }
        }
    }

    return maxLen
}