algo12 动态规划（下）— exercise.py 练习指南

Download exercise.py

练习目标

通过四个进阶 DP 练习题，掌握区间 DP、树形 DP、状态压缩 DP 和数位 DP 的设计模式。

预备知识

• 区间 DP 的按长度递增枚举模式
• 树形 DP 的后序遍历 + 状态聚合模式
• 状态压缩 DP 的二进制位运算
• 数位 DP 的 DFS + 记忆化搜索模板

任务清单

任务1：最长回文子序列 longest_palindromic_subsequence(s)

• 状态：dp[i][j] = s[i..j] 的最长回文子序列长度
• 转移：
  • s[i] == s[j]：两端字符相同，可以同时纳入 → dp[i+1][j-1] + 2
  • s[i] != s[j]：至少一端不能用 → max(dp[i+1][j], dp[i][j-1])
• 初始化：dp[i][i] = 1（单个字符是回文）
• 回溯：从 dp[0][n-1] 开始，根据转移来源决定包含哪些字符。

任务2：树的最小顶点覆盖 tree_min_vertex_cover(n, edges)

• 问题：选最少的节点使得每条边至少有一个端点被选中。
• 与最大独立集的关系：在任意图中，最小顶点覆盖 + 最大独立集 = 总节点数。但注意：等式只在一般图中成立需要二分图条件。在树中（树是二分图），可直接用 $VC=n-MIS$，也可以独立 DP。
• 独立 DP 状态：
  • dp[u][1] = 1 + sum(min(dp[v][0], dp[v][1]))（选了 u，子节点自由）
  • dp[u][0] = sum(dp[v][1])（不选 u，所有子节点必须选——否则边(u,v) 没有端点被覆盖）

任务3：状态压缩 DP — 集合划分

• 思路：枚举所有子集 mask，预计算每个子集的和 subset_sum[mask]。
• DP：dp[mask] = 已安排 mask 中元素后，最小化的最大子集和。
• 转移：枚举 mask 的子集 sub → dp[mask] = min(dp[mask], max(dp[mask ^ sub], subset_sum[sub]))

任务4：数位 DP — 各位乘积

• 模板：定义 dfs(pos, tight, leading_zero, product) 返回满足乘积条件且不越界的数的个数。
• 关键问题：如果 target_product 很大（如 > 81），许多 branch 会直接剪枝（因为 9 位以内数字的各位乘积最大是 $9^9$）。
• 记忆化：用 @lru_cache 或自定义 dict 存储 (pos, tight, product)。

提示

1. 最长回文子序列注意初始化 dp[i][i]=1 和 dp[i][i-1]=0（空区间）。
2. 树的最小顶点覆盖中，DFS 遍历时注意避免访问父节点。
3. 状态压缩中子集枚举的高效写法：sub = (sub - 1) & mask。

# -*- coding: utf-8 -*-
"""
algo12 动态规划（下）— 练习代码
===============================
请完成以下 TODO 任务，巩固进阶 DP 专题。
"""


# ============================================================================
# TODO 1: 最长回文子序列（区间 DP 变体）
# ============================================================================
def longest_palindromic_subsequence(s):
    """
    求字符串 s 的最长回文子序列（不要求连续）的长度。
    这是区间 DP 的经典应用。

    状态: dp[i][j] = s[i..j] 的最长回文子序列长度
    转移:
      - s[i] == s[j] → dp[i][j] = dp[i+1][j-1] + 2
      - s[i] != s[j] → dp[i][j] = max(dp[i+1][j], dp[i][j-1])

    参数:
        s: 输入字符串
    返回:
        最长回文子序列长度，以及该子序列本身
    """
    n = len(s)
    if n == 0:
        return 0, ''

    # TODO: 初始化 dp 表 (n x n)
    # dp[i][i] = 1  (单个字符是长度为 1 的回文)

    # TODO: 按长度递增填表
    # 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])

    # TODO: 回溯构建回文子序列
    return 0, ''  # TODO


# ============================================================================
# TODO 2: 树上的最小顶点覆盖
# ============================================================================
def tree_min_vertex_cover(n, edges):
    """
    树的最小顶点覆盖：选最少的节点，使每条边至少有一个端点被选中。
    与最大独立集互为补集：最小顶点覆盖 = n - 最大独立集。

    状态: dp[u][0] = 不选 u 时 u 子树的最小覆盖节点数
           dp[u][1] = 选 u 时 u 子树的最小覆盖节点数
    转移:
           dp[u][1] = 1 + sum(min(dp[v][0], dp[v][1]))
           dp[u][0] = sum(dp[v][1])  (不选 u，则所有子节点 v 必须选！)

    参数:
        n: 节点数
        edges: 边列表
    返回:
        最小覆盖集的大小
    """
    # TODO: 构建邻接表，DFS 后序遍历
    # TODO: 实现 dp 转移
    return 0  # TODO


# ============================================================================
# TODO 3: 状态压缩 DP — 集合划分问题
# ============================================================================
def min_set_partition(arr):
    """
    将数组划分为 k 个子集，使得各子集的和尽可能相等（最小化最大子集和）。
    使用状态压缩 DP。

    dp[mask] = 已安排的元素的子集和的最小可能最大值

    提示：先枚举所有子集的和，然后 DP

    参数:
        arr: 整数列表
    返回:
        最小的最大子集和
    """
    # TODO: 实现
    pass


# ============================================================================
# TODO 4: 数位 DP — 统计各位乘积
# ============================================================================
def count_numbers_by_digit_product(L, R, target_product):
    """
    统计 [L, R] 内各位数字乘积等于 target_product 的数的个数。
    使用数位 DP 模板。

    参数:
        L, R: 区间边界
        target_product: 目标乘积
    返回:
        满足条件的数的个数
    """
    # TODO: 实现 count_up_to(N, product) 辅助函数
    # 然后返回 count_up_to(R) - count_up_to(L-1)
    return 0  # TODO


# ============================================================================
# 测试代码
# ============================================================================
if __name__ == '__main__':
    print('=' * 50)
    print('algo12 动态规划（下）— 练习')
    print('=' * 50)

    # 测试 TODO 1: 最长回文子序列
    print('\n--- TODO 1: 最长回文子序列 ---')
    for s in ['bbbab', 'cbbd', 'a']:
        length, seq = longest_palindromic_subsequence(s)
        print(f'  s="{s}" → 长度={length}, 序列="{seq}"')
    # 期望: "bbbab" → 4 ("bbbb"), "cbbd" → 2 ("bb"), "a" → 1 ("a")

    # 测试 TODO 2: 树的最小顶点覆盖
    print('\n--- TODO 2: 树的最小顶点覆盖 ---')
    n = 4
    edges = [(0, 1), (0, 2), (1, 3)]
    vc = tree_min_vertex_cover(n, edges)
    print(f'  边={edges}, 最小顶点覆盖大小={vc}')

    # 测试 TODO 3: 集合划分
    print('\n--- TODO 3: 状态压缩 — 集合划分 ---')
    print(f'  {min_set_partition([3, 1, 4, 2, 2, 1])} (待实现)')

    # 测试 TODO 4: 数位 DP — 各位乘积
    print('\n--- TODO 4: 数位 DP — 各位数字乘积 ---')
    print(f'  [1, 100] 中各位积=0 的数: '
          f'{count_numbers_by_digit_product(1, 100, 0)} (待实现)')

    print('\n提示: 请补全上方所有 TODO 函数后再运行测试。')