Chuoer47's Blog

Appearance

算法模板 - 动态规划 ​

本文整理动态规划相关的算法模板，按难度递增排列：背包问题系列 → LIS → 数位 DP → 换根 DP → SOS-DP。

1. 0/1 背包 ​

问题：n 个物品，每个物品有重量和价值，背包容量为 V，每个物品最多选一次，求最大价值。

状态定义：dp[j] = 容量为 j 时的最大价值。

状态转移：dp[j] = max(dp[j], dp[j-w] + v)——要么不选（dp[j]），要么选（dp[j-w] + v）。

python
def knapsack_01(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for j in range(capacity, weights[i] - 1, -1):  # 逆序！
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[capacity]

为什么逆序？ 正序遍历时，dp[j - w] 可能已经被当前物品更新过，相当于"选了两次"。逆序保证 dp[j - w] 还是上一轮的值，每个物品最多选一次。

如果改成正序？ 就变成了完全背包（每个物品可以选无限次）。

2. 分组背包 ​

问题：物品被分成若干组，每组内最多选一个物品。

状态转移：在 0/1 背包的基础上多一层循环——对每组，遍历容量，再遍历组内物品。

python
def group_knapsack(capacity, groups):
    """
    分组背包

    参数:
        capacity: 背包容量
        groups: 物品分组，每个组是 [[weight, value], ...]
    """
    dp = [0] * (capacity + 1)
    for group in groups:
        for j in range(capacity, -1, -1):       # 逆序遍历容量
            for weight, value in group:           # 遍历组内物品
                if weight <= j:
                    dp[j] = max(dp[j], dp[j - weight] + value)
    return dp[capacity]

# 示例
capacity = 10
groups = [
    [[2, 3], [3, 4]],   # 第一组
    [[4, 5], [5, 6]],   # 第二组
    [[6, 7]]             # 第三组
]
print(group_knapsack(capacity, groups))  # 13

设计要点：外层遍历组，中层逆序遍历容量，内层遍历组内物品。这个顺序保证每组最多选一个——中层逆序确保同一组的物品不会被重复选。

3. 多重背包（单调队列优化） ​

问题：每个物品有数量限制 s_i，朴素做法 O(nVs) 超时。

优化思路：按余数分组，对每组用单调队列维护滑动窗口最大值，将复杂度降到 O(nV)。

python
from collections import deque

def knapsack_multiple(n, v, items):
    """
    多重背包（单调队列优化）

    参数:
        n: 物品种数
        v: 背包容量
        items: [(vi, wi, si), ...] 每种物品的重量、价值、数量
    """
    dp = [0] * (v + 1)
    for vi, wi, si in items:
        pre = dp.copy()
        for r in range(vi):  # 按余数分组
            q = deque()
            for j in range(r, v + 1, vi):  # 同余的容量
                # 弹出不在窗口内的元素
                while q and (j - q[0]) // vi > si:
                    q.popleft()
                # 维护单调性
                while q and pre[q[-1]] - (q[-1] - r) // vi * wi <= pre[j] - (j - r) // vi * wi:
                    q.pop()
                q.append(j)
                dp[j] = max(dp[j], pre[q[0]] + (j - q[0]) // vi * wi)
    return dp[v]

单调队列在这里做什么？ 对于同余的容量位置 j, j-vi, j-2vi, ...，dp[j] 的转移来自 pre[j-k*vi] + k*wi（k ≤ s_i）。单调队列在 O(1) 时间内给出这个窗口的最大值。

4. 混合背包 ​

问题：同时存在 0/1 物品、完全物品（无限个）、多重物品（有限个）。

思路：分类型处理——0/1 物品用逆序遍历，完全物品用正序遍历，多重物品用单调队列。

python
from collections import deque

def mixed_knapsack(n, v, items):
    """
    混合背包

    参数:
        n: 物品种数
        v: 背包容量
        items: [(vi, wi, si), ...]  si=-1 表示完全物品，si=0 表示 0/1 物品，si>0 表示多重物品
    """
    dp = [0] * (v + 1)
    for vi, wi, si in items:
        if si == -1:
            # 完全物品：正序遍历（可以选无限次）
            for j in range(vi, v + 1):
                dp[j] = max(dp[j], dp[j - vi] + wi)
        elif si == 0:
            # 0/1 物品：逆序遍历（最多选一次）
            for j in range(v, vi - 1, -1):
                dp[j] = max(dp[j], dp[j - vi] + wi)
        else:
            # 多重物品：单调队列优化
            pre = dp.copy()
            for r in range(vi):
                q = deque()
                for j in range(r, v + 1, vi):
                    while q and (j - q[0]) // vi > si:
                        q.popleft()
                    while q and pre[q[-1]] - (q[-1] - r) // vi * wi <= pre[j] - (j - r) // vi * wi:
                        q.pop()
                    q.append(j)
                    dp[j] = max(dp[j], pre[q[0]] + (j - q[0]) // vi * wi)
    return dp[v]

5. 最长上升子序列（LIS） ​

5.1 O(n²) DP ​

状态定义：dp[i] = 以 nums[i] 结尾的 LIS 长度。

python
def lis_dp(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

5.2 O(n log n) 贪心 + 二分 ​

核心思想：维护一个栈 stack，stack[i] 表示长度为 i+1 的上升子序列的最小末尾。对每个新元素，如果比栈顶大就入栈，否则用二分找到第一个 ≥ 它的位置替换。

python
import bisect

def lis_nlogn(nums):
    stack = []
    for num in nums:
        if not stack or num > stack[-1]:
            stack.append(num)
        else:
            stack[bisect.bisect_left(stack, num)] = num
    return len(stack)

为什么替换是正确的？ 替换不会改变 LIS 的长度，但让"结尾更小"，给后续元素更多空间。这是一种贪心策略——尽可能让每个长度的 LIS 结尾最小。

如果要求非严格递增（可以相等）？ 把 bisect_left 改成 bisect_right 即可。

6. 数位 DP ​

适用场景：统计 [low, high] 中满足某条件的数字个数。

核心思想：逐位枚举，用 limit_low 和 limit_high 控制当前位的上下界，@cache 记忆化。

python
from functools import cache

def digit_count(low: int, high: int, target: int) -> int:
    """统计 [low, high] 中恰好包含 target 个 0 的数字个数"""
    low_s = list(map(int, str(low)))
    high_s = list(map(int, str(high)))
    n = len(high_s)
    diff = n - len(low_s)  # low 和 high 的位数差

    @cache
    def dfs(i: int, cnt0: int, limit_low: bool, limit_high: bool) -> int:
        if cnt0 > target:
            return 0
        if i == n:
            return 1 if cnt0 == target else 0

        lo = low_s[i - diff] if limit_low and i >= diff else 0
        hi = high_s[i] if limit_high else 9

        res = 0
        # 处理前导零（如果 low 位数少于 high）
        if limit_low and i < diff:
            res = dfs(i + 1, cnt0, True, False)
            lo = 1

        for d in range(lo, hi + 1):
            res += dfs(
                i + 1,
                cnt0 + (1 if d == 0 else 0),
                limit_low and d == lo,
                limit_high and d == hi,
            )
        return res

    return dfs(0, 0, True, True)

# 示例
print(digit_count(0, 10, 1))   # 2（数字 0 和 10）
print(digit_count(10, 20, 1))  # 1（数字 10）

数位 DP 的四个参数：

  • i：当前处理到第几位
  • cnt0：已经用了多少个 0
  • limit_low：当前是否受下界约束（不能填比 low 当前位更小的）
  • limit_high：当前是否受上界约束（不能填比 high 当前位更大的）

前导零处理：当 low 的位数少于 high 时，需要特殊处理前导零。limit_low and i < diff 表示"当前位还在 low 的前导零范围内"。

7. 换根 DP ​

适用场景：树上问题，需要以每个节点为根计算答案。

核心思想：两次 DFS。第一次以任意节点为根计算"子树内"的答案。第二次"换根"——当根从 u 移到邻居 v 时，用 O(1) 的公式更新答案。

python
def sum_of_distances(n: int, edges: list) -> list:
    """LeetCode 834. 求树中每个节点到其他所有节点的距离之和"""
    g = [[] for _ in range(n)]
    for x, y in edges:
        g[x].append(y)
        g[y].append(x)

    ans = [0] * n
    size = [1] * n  # 子树大小

    def dfs(node: int, fa: int, depth: int) -> None:
        """第一次 DFS：计算 ans[0]（以 0 为根）和每个子树的大小"""
        ans[0] += depth
        for nxt in g[node]:
            if nxt == fa:
                continue
            dfs(nxt, node, depth + 1)
            size[node] += size[nxt]

    def reroot(node: int, fa: int) -> None:
        """第二次 DFS：换根，用公式计算其他节点的答案"""
        for nxt in g[node]:
            if nxt == fa:
                continue
            # 核心公式
            ans[nxt] = ans[node] + n - 2 * size[nxt]
            reroot(nxt, node)

    dfs(0, -1, 0)
    reroot(0, -1)
    return ans

换根公式推导：当根从 node 移到 nxt 时：

  • nxt 的子树内（size[nxt] 个节点）：距离都减 1
  • 其余节点（n - size[nxt] 个）：距离都加 1
  • 所以 ans[nxt] = ans[node] - size[nxt] + (n - size[nxt]) = ans[node] + n - 2 * size[nxt]

8. SOS-DP（子集/超集 DP） ​

适用场景：枚举所有子集或超集的聚合运算。把"枚举所有子集"从 O(3^n) 优化到 O(n · 2^n)。

python
class SOSDP:
    def __init__(self, n: int):
        """n = 比特数，数组大小为 2^n"""
        self.n = n
        self.N = 1 << n
        self.f = [0] * self.N

    def subset_sum(self):
        """子集和：f[mask] = Σ f[sub]（sub 是 mask 的子集）"""
        for i in range(self.n):
            bit = 1 << i
            for mask in range(self.N):
                if mask & bit:
                    self.f[mask] += self.f[mask ^ bit]

    def superset_sum(self):
        """超集和：f[mask] = Σ f[sup]（sup 是 mask 的超集）"""
        for i in range(self.n):
            bit = 1 << i
            for mask in range(self.N):
                if not (mask & bit):
                    self.f[mask] += self.f[mask | bit]

SOS-DP 的本质：逐位决策——对每个 bit，选择"包含"或"不包含"。外层枚举 bit，内层枚举 mask，保证每个子集只被计算一次。

总结 ​

算法时间复杂度核心思想
0/1 背包O(nV)逆序遍历容量
分组背包O(nV · 组内物品数)外组中容内物
多重背包（单调队列）O(nV)按余数分组 + 滑动窗口
混合背包O(nV)分类型处理
LIS（二分）O(n log n)维护最小末尾栈
数位 DPO(n · 状态数)逐位枚举 + 记忆化
换根 DPO(n)两次 DFS + 换根公式
SOS-DPO(n · 2^n)逐位决策

模板源码：AlgorithmLearning