算法知识图谱总览 / 动态规划基础族 / 计数DP

计数DP

P1intermediatestandardG-A-11
← 上一个 / 组内dp-state 组内第 12 / 15返回组索引 全局返回总览 下一个 / 组内dp-number

What · 是什么

利用DP记忆化求计数问题，划分子集不重不漏

计数DP是一种利用类似DP的记忆化方法解决计数（和求和）问题的技术。与最优化DP的关键区别在于：计数问题要求将状态空间划分为若干两两无交的子集（不重不漏），而最优化DP只需子集的并覆盖全集即可。典型问题包括整数划分、路径计数、组合数计算等。

Why · 为什么

直觉 · Intuition

如果集合S可以划分为两两无交的子集S1,S2,...,Sk，则|S|=|S1|+|S2|+...+|Sk|。关键是找到一种划分方式使得每个子集的计数与原问题同构（规模更小的同类问题），从而可以用记忆化递推求解。

原理 · Principle

基本范式：f(S)=sum{f(S_i)} 其中S=并集(S_i)且S_i两两无交。与最优化DP的区别：max可以取任意划分(只需覆盖全集)，但计数要求不重不漏。整数划分：f(n,M)=f(n,M-1)+f(n-M,M)（含M与不含M两类，不重叠）。状态转移方程确定后用递推或记忆化搜索计算。

历史 · History

计数DP是竞赛中处理大规模计数问题的核心技术。OI Wiki将其与最优化DP对比，强调了「不重不漏」的划分要求。整数划分问题是最经典的计数DP教学案例，从O(n²)到O(n^{3/2})有多种优化。

How · 实现

伪代码

# 整数划分(顺序不同算同一种)
# f(n, M) = 将n划分为不超过M的正整数的方案数
f(n, M) = f(n, M-1) + f(n-M, M) if n >= M else f(n, M-1)
# 边界: f(0, M)=1, f(n, 0)=0 (n>0)
# 优化: 滚动数组

Python 实现

def integer_partition(n):
    """整数划分: 将n划分为若干正整数之和的方案数(顺序无关)
    如 n=4: 4=3+1=2+2=2+1+1=1+1+1+1, 共5种
    f(n, M) = f(n, M-1) + f(n-M, M)  (不含M + 含M)
    """
    f = [0] * (n + 1)
    f[0] = 1
    for M in range(1, n + 1):  # 枚举最大数
        for j in range(M, n + 1):
            f[j] += f[j - M]
    return f[n]


def integer_partition_ordered(n):
    """有序整数划分(顺序不同算不同种)
    如 n=4: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 1+3, 3+1, 2+2, 4 = 8种
    g(n) = 2^(n-1) (n>=1)
    """
    if n == 0:
        return 1
    return 1 << (n - 1)


def count_paths(n, m):
    """网格路径计数: 从(0,0)到(n-1,m-1)只向下向右走的方案数
    C(n+m-2, n-1)
    """
    f = [[0] * m for _ in range(n)]
    f[0][0] = 1
    for i in range(n):
        for j in range(m):
            if i > 0:
                f[i][j] += f[i - 1][j]
            if j > 0:
                f[i][j] += f[i][j - 1]
    return f[n - 1][m - 1]


if __name__ == "__main__":
    # 整数划分测试
    assert integer_partition(4) == 5, f"Expected 5, got {integer_partition(4)}"
    assert integer_partition(1) == 1
    # 5的划分: {5},{4,1},{3,2},{3,1,1},{2,2,1},{2,1,1,1},{1,1,1,1,1} = 7
    assert integer_partition(5) == 7, f"Expected 7, got {integer_partition(5)}"
    assert integer_partition(6) == 11

    # 有序划分
    assert integer_partition_ordered(4) == 8
    assert integer_partition_ordered(1) == 1

    # 路径计数
    assert count_paths(3, 3) == 6  # C(4,2)=6
    assert count_paths(2, 2) == 2
    assert count_paths(1, 1) == 1

    print("All tests passed.")
PyPy 提示PyPy对列表操作和整数加法快，n=5000的整数划分约0.1s。注意结果可能很大，Python天然支持大整数无需取模处理。
时间复杂度整数划分: O(n²) → O(n^{3/2})优化；路径计数: O(nm)
空间复杂度O(n) 滚动数组
注意 · 局限结果可能极大需取模。整数划分O(n²)在n>1e4时Python慢。计数DP的正确性核心在于不重不漏的划分证明，容易出错。

易错点

例题

OJ题号难度考点链接
LuoguP10252NOIP2001 数的划分：将n划分为k个正整数的方案数，计数DPhttps://www.luogu.com.cn/problem/P1025
LeetCode621不同路径：网格路径计数DP入门https://leetcode.cn/problems/unique-paths/
步骤迷你图（节点 = 算法步骤 · 边 = 流程 · 绿色 = 起始步骤）
上游 · 本知识点依赖（前置/变体/组合/共现）
动态规划基础前置依赖前缀和与差分组合

信源

✓ = 已核验 · △ = 未核验