学习笔记

动态规划 ​

#算法 · #动态规划 · #DP · #背包 · #LCS · #子序列

动态规划（Dynamic Programming）将复杂问题分解为重叠子问题，通过记忆化避免重复计算，是算法设计的核心范式。从爬楼梯到背包问题，从 LCS 到编辑距离，DP 无处不在。

核心思想 ​

DP 四要素 ​

1. 状态定义：dp[i] 或 dp[i][j] 表示什么？
2. 状态转移方程：dp[i] = f(dp[i-1], ...)
3. 初始条件：dp[0] = ?
4. 计算顺序：正向？反向？斜向？

DP vs 分治 vs 贪心 ​

维度分治DP贪心
子问题关系独立重叠无回溯
最优子结构需要需要需要
记忆化不需要核心不需要
是否正确总是总是不一定

通用模板 ​

python
# 自顶向下（记忆化搜索）
memo = {}
def dp(state):
    if state in memo:
        return memo[state]
    if base_case(state):
        return base_value
    result = optimal(dp(sub_state) for each possible choice)
    memo[state] = result
    return result

# 自底向上（迭代填表）
def dp_bottom_up(n):
    dp = [0] * (n + 1)
    dp[0] = base_value
    for i in range(1, n + 1):
        dp[i] = optimal(dp[i-k] + cost for each choice)
    return dp[n]

经典问题 ​

1. 斐波那契 / 爬楼梯 ​

go
// 问题：每次爬 1 或 2 阶，到第 n 阶有多少种方法？
func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    dp := make([]int, n+1)
    dp[1], dp[2] = 1, 2
    for i := 3; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

// 空间优化 O(1)
func climbStairsOptimized(n int) int {
    if n <= 2 {
        return n
    }
    a, b := 1, 2
    for i := 3; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

2. 背包问题 ​

0-1 背包 ​

go
// 给定 n 个物品，重量 w[i]，价值 v[i]，容量 W，求最大价值
func knapsack01(weights, values []int, W int) int {
    n := len(weights)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, W+1)
    }
    for i := 1; i <= n; i++ {
        for j := 0; j <= W; j++ {
            if j < weights[i-1] {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
            }
        }
    }
    return dp[n][W]
}

// 空间优化：一维滚动数组，反向遍历
func knapsack01Optimized(weights, values []int, W int) int {
    dp := make([]int, W+1)
    for i := 0; i < len(weights); i++ {
        for j := W; j >= weights[i]; j-- {
            dp[j] = max(dp[j], dp[j-weights[i]]+values[i])
        }
    }
    return dp[W]
}

完全背包（每件物品无限次） ​

go
func knapsackComplete(weights, values []int, W int) int {
    dp := make([]int, W+1)
    for i := 0; i < len(weights); i++ {
        for j := weights[i]; j <= W; j++ { // 正向遍历！
            dp[j] = max(dp[j], dp[j-weights[i]]+values[i])
        }
    }
    return dp[W]
}

3. 最长公共子序列（LCS） ​

go
// dp[i][j] = text1[0..i) 和 text2[0..j) 的 LCS 长度
func longestCommonSubsequence(text1, 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 {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[m][n]
}

4. 最长递增子序列（LIS） ​

go
// O(n²) 暴力 DP
func lengthOfLIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    maxLen := 0
    for i := 0; i < n; i++ {
        dp[i] = 1
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        maxLen = max(maxLen, dp[i])
    }
    return maxLen
}

// O(n log n) 贪心 + 二分（耐心排序）
func lengthOfLISOptimized(nums []int) int {
    tails := []int{}
    for _, x := range nums {
        // 二分查找 tails 中第一个 >= x 的位置
        idx := sort.Search(len(tails), func(i int) bool { return tails[i] >= x })
        if idx == len(tails) {
            tails = append(tails, x)
        } else {
            tails[idx] = x
        }
    }
    return len(tails)
}

5. 编辑距离（Levenshtein Distance） ​

go
// word1 转换为 word2 的最少操作数（插入/删除/替换）
func minDistance(word1, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
            }
        }
    }
    return dp[m][n]
}

DP 分类与识别技巧 ​

类型特征典型问题
线性 DPdp[i] 只依赖 dp[i-1] 或 dp[i-2]爬楼梯、打家劫舍
区间 DPdp[i][j] 表示区间 [i,j]矩阵链乘法、石子合并
背包 DP选择物品，容量约束0-1 背包、完全背包
状态机 DP状态 + 转移股票买卖（多次、含冷冻期）
树形 DP在树上自底向上二叉树最大路径和、树的最小支配集
状压 DP状态压缩为 bitmaskTSP、集合覆盖
数位 DP按位统计1~n 中 1 的出现次数
概率 DPdp[i] = Σ(p * dp[j])期望步数、抛硬币

识别标志 ​

问题中出现以下关键词 → 考虑 DP：
1. "最长"、"最大"、"最小"、"最少"
2. "多少种方法"、"方案数"
3. "是否存在"
4. 问题可分解为重叠子问题
5. 数据规模 n ≤ 10^4（暗示 O(n²) 或 O(n log n) DP）

DP 优化技巧 ​

技巧场景效果
滚动数组dp[i] 只依赖 dp[i-1]O(n×m) → O(m) 空间
单调队列滑动窗口内求最值O(n²) → O(n)
斜率优化形如 dp[i] = min(dp[j] + f(j) + g(i))O(n²) → O(n)
四边形不等式区间 DP 决策单调O(n³) → O(n²)
矩阵快速幂线性递推O(n) → O(log n)
bitset背包可达性O(nW) → O(nW/64)

进阶专题 ​

6. 区间 DP ​

核心思想 ​

dp[i][j] 表示区间 [i, j] 上的最优解
从长度 len=1 开始，逐步扩大区间，最终求 dp[0][n-1]

通用模板：
for len := 2; len <= n; len++ {         // 枚举区间长度
    for i := 0; i+len-1 < n; i++ {      // 枚举起点
        j := i + len - 1                // 终点
        for k := i; k < j; k++ {        // 枚举分割点
            dp[i][j] = merge(dp[i][k], dp[k+1][j])
        }
    }
}

戳气球（Burst Balloons） ​

go
// 有 n 个气球，编号 0..n-1，戳破 i 得分 = nums[i-1]*nums[i]*nums[i+1]
// 求最大得分
func maxCoins(nums []int) int {
    n := len(nums)
    // 两边加 1（边界虚拟气球）
    arr := make([]int, n+2)
    arr[0], arr[n+1] = 1, 1
    copy(arr[1:], nums)

    dp := make([][]int, n+2)
    for i := range dp {
        dp[i] = make([]int, n+2)
    }

    // len: 从短到长
    for length := 1; length <= n; length++ {
        for i := 1; i+length-1 <= n; i++ {
            j := i + length - 1
            // k 是区间 [i,j] 中最后一个被戳破的气球
            for k := i; k <= j; k++ {
                score := arr[i-1]*arr[k]*arr[j+1] + dp[i][k-1] + dp[k+1][j]
                if score > dp[i][j] {
                    dp[i][j] = score
                }
            }
        }
    }
    return dp[1][n]
}

矩阵链乘法 ​

go
// 给定矩阵维度 dims[0..n]，矩阵 i 的维度为 dims[i-1] x dims[i]
// 求最少乘法次数
func matrixChainOrder(dims []int) int {
    n := len(dims) - 1
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    for length := 2; length <= n; length++ {
        for i := 0; i+length-1 < n; i++ {
            j := i + length - 1
            dp[i][j] = math.MaxInt
            for k := i; k < j; k++ {
                cost := dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                if cost < dp[i][j] {
                    dp[i][j] = cost
                }
            }
        }
    }
    return dp[0][n-1]
}

7. 状态机 DP ​

股票买卖系列 ​

go
// 最多交易 2 次，求最大利润
func maxProfit(prices []int) int {
    n := len(prices)
    // dp[i][k][0] = 第 i 天、交易 k 次、不持有股票的最大利润
    // dp[i][k][1] = 第 i 天、交易 k 次、持有股票的最大利润
    maxK := 2
    dp := make([][][]int, n)
    for i := range dp {
        dp[i] = make([][]int, maxK+1)
        for k := range dp[i] {
            dp[i][k] = make([]int, 2)
        }
    }

    for i := 0; i < n; i++ {
        for k := maxK; k >= 1; k-- {
            if i == 0 {
                dp[i][k][0] = 0
                dp[i][k][1] = -prices[i]
                continue
            }
            dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
            dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
        }
    }
    return dp[n-1][maxK][0]
}

状态机通用模板 ​

go
// 有限状态自动机 DP
// 适用于：状态有限、状态转移明确的场景

// 例：打家劫舍（不能偷相邻）
func rob(nums []int) int {
    n := len(nums)
    // dp[i][0] = 不偷 i
    // dp[i][1] = 偷 i
    dp := make([][2]int, n+1)
    dp[0][0], dp[0][1] = 0, 0 // 哨兵

    for i := 0; i < n; i++ {
        dp[i+1][0] = max(dp[i][0], dp[i][1])           // 不偷：取前一天最大值
        dp[i+1][1] = dp[i][0] + nums[i]                // 偷：前一天必须没偷
    }
    return max(dp[n][0], dp[n][1])
}

8. 状压 DP（Bitmask DP） ​

go
// 旅行商问题 (TSP)：从 0 出发，访问所有城市，求最短路径
func tsp(dist [][]int) int {
    n := len(dist)
    // dp[mask][i] = 已访问城市集合为 mask、目前在 i
    dp := make([][]int, 1<<n)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = math.MaxInt
        }
    }
    dp[1][0] = 0 // 只访问了城市 0

    for mask := 0; mask < (1 << n); mask++ {
        for u := 0; u < n; u++ {
            if dp[mask][u] == math.MaxInt {
                continue
            }
            for v := 0; v < n; v++ {
                if mask>>v&1 == 1 {
                    continue // 已访问过
                }
                newMask := mask | (1 << v)
                if dp[mask][u]+dist[u][v] < dp[newMask][v] {
                    dp[newMask][v] = dp[mask][u] + dist[u][v]
                }
            }
        }
    }

    // 回到起点 0
    ans := math.MaxInt
    for u := 0; u < n; u++ {
        ans = min(ans, dp[(1<<n)-1][u]+dist[u][0])
    }
    return ans
}

9. 树形 DP ​

go
// 二叉树中的最大路径和
func maxPathSum(root *TreeNode) int {
    maxSum := math.MinInt

    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := max(0, dfs(node.Left))    // 负贡献放弃
        right := max(0, dfs(node.Right))

        // 经过 node 的完整路径
        maxSum = max(maxSum, left+right+node.Val)

        // 向上返回单边最大值（父节点只能用一边）
        return node.Val + max(left, right)
    }

    dfs(root)
    return maxSum
}

面试高频题 ​

  1. 爬楼梯 — 理解 DP 基本框架
  2. 0-1 背包 — 二维 → 一维空间优化
  3. 最长回文子串 — 中心扩展 vs DP vs Manacher
  4. 正则表达式匹配 — 二维 DP + 特殊情况
  5. 戳气球 — 区间 DP 经典题
  6. 鸡蛋掉落 — 经典二分 + DP 思维
  7. 分割等和子集 — 背包变种
  8. 最长递增子序列 — DP + 二分优化

Hard 题完整代码 ​

编辑距离（Edit Distance / Levenshtein Distance） ​

go
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp { dp[i] = make([]int, n+1) }

    // base case: 空串 → 另一个串需要全部插入/删除
    for i := 0; i <= m; i++ { dp[i][0] = i }
    for j := 0; j <= n; j++ { dp[0][j] = j }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            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],   // 删除 word1[i-1]
                    dp[i][j-1],   // 插入 word2[j-1] 到 word1
                    dp[i-1][j-1], // 替换 word1[i-1] 为 word2[j-1]
                )
            }
        }
    }
    return dp[m][n]
}
mermaid
flowchart TB
    subgrid ED["编辑距离 dp 表 — 'horse' → 'ros'"]
        direction LR
        D["   '' r  o  s<br/>'' 0  1  2  3<br/>h  1  1  2  3<br/>o  2  2  1  2<br/>r  3  2  2  2<br/>s  4  3  3  2<br/>e  5  4  4  3"]
    end

    subgraph path["最优操作序列"]
        P1["h → 删除 (dp[1][0]→dp[0][0])"]
        P2["o → o 跳过 (dp[2][2]→dp[1][1])"]
        P3["r → r 跳过"]
        P4["s → 替换 e→s (dp[4][4]→dp[3][3])"]
        P5["结果: 3 步"]
    end

正则表达式匹配 ​

go
func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    dp := make([][]bool, m+1)
    for i := range dp { dp[i] = make([]bool, n+1) }

    dp[0][0] = true // 空串匹配空模式

    // base case: s="" 时，p 必须是 a*b* 这种可匹配空的结构
    for j := 1; j <= n; j++ {
        if p[j-1] == '*' {
            dp[0][j] = dp[0][j-2] // '*' 匹配零个前驱
        }
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if p[j-1] == '*' {
                // 两种情况: '*' 匹配零次 → dp[i][j-2]
                //            '*' 匹配 N 次 → 当前字符匹配 && dp[i-1][j]
                dp[i][j] = dp[i][j-2] ||
                    (match(s[i-1], p[j-2]) && dp[i-1][j])
            } else {
                dp[i][j] = match(s[i-1], p[j-1]) && dp[i-1][j-1]
            }
        }
    }
    return dp[m][n]
}

func match(a byte, b byte) bool {
    return b == '.' || a == b
}
text
正则 DP 的核心难点 — '*' 的两种含义:
  1. 匹配零次前驱: dp[i][j] = dp[i][j-2]
     例: s="a", p="ab*" → b* 匹配 0 次 b → 等价于 p="a"

  2. 匹配一次或多次: s[i-1] == p[j-2] || p[j-2] == '.'
     dp[i][j] = dp[i-1][j] (注意是 dp[i-1][j]，不是 dp[i-1][j-2]！)
     例: s="aa", p="a*" → a* 匹配 2 次 a

  关键: dp[i-1][j] 意味着"消掉 s 的一个字符后，p 不变（仍以 * 结尾）"

戳气球（Burst Balloons — 区间 DP） ​

go
func maxCoins(nums []int) int {
    n := len(nums)
    // 两端补 1（边界气球）
    balloons := make([]int, n+2)
    balloons[0], balloons[n+1] = 1, 1
    copy(balloons[1:], nums)

    dp := make([][]int, n+2)
    for i := range dp { dp[i] = make([]int, n+2) }

    // 区间 DP: 按长度递推
    for length := 1; length <= n; length++ {
        for left := 1; left <= n-length+1; left++ {
            right := left + length - 1
            // k 是区间内最后被戳破的气球
            for k := left; k <= right; k++ {
                coins := balloons[left-1]*balloons[k]*balloons[right+1] +
                         dp[left][k-1] + dp[k+1][right]
                if coins > dp[left][right] {
                    dp[left][right] = coins
                }
            }
        }
    }
    return dp[1][n]
}
text
区间 DP 解法思路:
  正向想"先戳哪个": 子问题不独立，因为戳破后邻居变了
  反向想"最后戳哪个": 当 k 是区间 [left, right] 中最后被戳破的，
    → 左右邻居必定是 left-1 和 right+1（区间外的气球）
    → dp[left][right] = max(balloons[left-1] × balloons[k] × balloons[right+1]
                             + dp[left][k-1] + dp[k+1][right])

DP 题型快速识别 ​

题型状态特征转移方向典型例题
线性 DPdp[i] 只依赖 dp[i-1]从左到右爬楼梯、打家劫舍
背包 DPdp[i][w] 二维/滚动数组物品→容量0-1 背包、完全背包
区间 DPdp[l][r] 按长度递推短→长戳气球、最长回文子序列
序列 DPdp[i][j] 两串匹配i,j 递增LCS、编辑距离、正则匹配
状态机 DPdp[i][state] 有限状态状态转移买卖股票 III、IV
树形 DPdfs(node) 后序遍历叶子→根二叉树最大路径和

参考 ​

批注模式

💬 文章评论

暂无评论，来说点什么吧 👇

编程学习笔记

Copyright © 2026