动态规划分类

动态规划分类详解

动态规划 (Dynamic Programming, DP) 是一种通过分解问题为子问题并利用最优子结构解决复杂问题的算法设计方法。根据问题特点，可以将动态规划分为以下几类。

---

1. 按问题类型分类

1.1 线性动态规划

特点：问题具有线性顺序的结构，状态转移只依赖于前一个或若干个状态。

常见问题：

• 斐波那契数列：状态转移 ( f(n) = f(n-1) + f(n-2) )。
• 最长上升子序列：状态转移 ( dp[i] = \max(dp[j] + 1) ) （满足 ( j < i ) 且 ( nums[j] < nums[i] )）。
• 背包问题：
  • 0-1 背包：物品只能选择一次。
  • 完全背包：物品可以选择无限次。

模板：

func fib(n int) int {
    if n <= 1 {
        return n
    }
    dp := make([]int, n+1)
    dp[0], dp[1] = 0, 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

---

1.2 区间动态规划

特点：问题涉及区间的划分和合并，通常定义 ( dp[i][j] ) 为区间 ([i, j]) 的某种性质。

常见问题：

• 戳气球问题：( dp[i][j] = \max(dp[i][k] + dp[k][j] + nums[i] \times nums[k] \times nums[j]) )。
• 回文子串个数：判断区间 ([i, j]) 是否为回文。
• 矩阵链乘积：区间内矩阵乘法的最小代价。

模板：

func minInsertions(s string) int {
    n := len(s)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for l := 2; l <= n; l++ {
        for i := 0; i+l-1 < n; i++ {
            j := i + l - 1
            if s[i] == s[j] {
                dp[i][j] = dp[i+1][j-1]
            } else {
                dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
            }
        }
    }
    return dp[0][n-1]
}

---

1.3 背包动态规划

特点：解决物品选择问题，通过容量的限制决定选择哪些物品。

分类：

• 01 背包：( dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) )。
• 完全背包：物品可选多次。
• 多重背包：物品可选固定次数。

模板：

func knapsack(weights, values []int, capacity int) int {
    n := len(weights)
    dp := make([]int, capacity+1)
    for i := 0; i < n; i++ {
        for j := capacity; j >= weights[i]; j-- {
            dp[j] = max(dp[j], dp[j-weights[i]] + values[i])
        }
    }
    return dp[capacity]
}

---

1.4 树形动态规划

特点：问题在树结构上递归求解，子问题依赖于树的子节点。

常见问题：

• 树的直径：求树的最长路径。
• 树上选点问题：如最小顶点覆盖、选点最大权值和。

模板：

func treeDiameter(edges [][]int) int {
    n := len(edges) + 1
    graph := make([][]int, n)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }
    var dfs func(node, parent int) int
    maxDiameter := 0
    dfs = func(node, parent int) int {
        max1, max2 := 0, 0
        for _, child := range graph[node] {
            if child == parent {
                continue
            }
            height := dfs(child, node) + 1
            if height > max1 {
                max1, max2 = height, max1
            } else if height > max2 {
                max2 = height
            }
        }
        maxDiameter = max(maxDiameter, max1+max2)
        return max1
    }
    dfs(0, -1)
    return maxDiameter
}

---

1.5 状态压缩动态规划

特点：利用二进制位压缩状态，适用于子集问题或排列问题。

常见问题：

• 旅行商问题 (TSP)。
• 子集分割问题。
• N 皇后问题。

模板：

func tsp(graph [][]int) int {
    n := len(graph)
    dp := make([][]int, 1<<n)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = 1<<31 - 1
        }
    }
    dp[1][0] = 0
    for mask := 1; mask < (1 << n); mask++ {
        for u := 0; u < n; u++ {
            if mask&(1<<u) == 0 {
                continue
            }
            for v := 0; v < n; v++ {
                if mask&(1<<v) == 0 {
                    dp[mask|(1<<v)][v] = min(dp[mask|(1<<v)][v], dp[mask][u]+graph[u][v])
                }
            }
        }
    }
    return dp[(1<<n)-1][0]
}

---

2. 按维度分类

1. 一维 DP：如斐波那契数列、爬楼梯问题。
2. 二维 DP：如最长公共子序列、编辑距离。
3. 多维 DP：如多重背包问题。
4. 滚动数组优化：减少空间复杂度，将二维 DP 压缩为一维。

---

3. 按问题特性分类

1. 路径类问题：最短路径、最小代价。
2. 计数类问题：统计方案数。
3. 划分类问题：区间划分、子集划分。
4. 匹配类问题：如正则表达式匹配。
5. 博弈类问题：如石子游戏。

---

总结

动态规划是算法中的一大分支，熟练掌握需要不断练习和总结。重点在于：

1. 明确状态定义与状态转移。
2. 发现重复子问题。
3. 优化时间与空间复杂度（如滚动数组、状态压缩）。

常见动态规划题目如背包问题、最长公共子序列、TSP 等都是经典入门点。