换个问题：不求「最好」，改数「多少种」

前面几类线性 DP 都在问同一句话——最优是多少：最长的子序列、最大的子段和、代价最小的对齐。所以它们的转移里都坐着一个 $\max$ （或 $\min$ ）。可现实里的问题未必都求极值：「上 $n$ 级楼梯，每步跨 1 或 2 级，有多少种走法？」「把 $n$ 拆成若干正整数，有几种拆法？」答案不再是一个「最好的值」，而是一个计数。

同一条链式转移，从「最优 DP」翻面成「计数 DP」只动两处：中间的算子 max → +，地基 f[0] 从 0 → 1。

关键洞察小到出乎意料：把转移里的 $\max$ 换成加法 $+$ ，DP 就从「记录最优」变成「累计方案」。道理在于 DP 的两大要件恰好都适配计数——最优子结构变成「大问题的方案由子问题的方案拼成」，无后效性保证「不同来路拼出的方案互不重复」。于是原来在若干候选里挑最大的那一步，现在变成把若干候选的方案数全部加起来。

先用一个极小的例子热身。上 $3$ 级台阶：走法有 $1{+}1{+}1$ 、 $1{+}2$ 、 $2{+}1$ 三种。若这是最优题，我们会问「最少几步」（答案 2 步）；而这里问「几种走法」，答案是 3——同一个状态骨架，读出的东西完全不同。这一节就把计数型线性 DP 讲透：先是数楼梯（一维斐波那契计数），再深入整数划分（二维计数），最后点一句高精度这个计数题的老搭档。

数楼梯：f[i] = f[i−1] + f[i−2]

设 $f[i]$ 表示跳到第 $i$ 级台阶的不同走法数。怎么递推？盯住最后一步：站在第 $i$ 级，上一步只可能来自两处——从第 $i-1$ 级跨 1 级上来，或从第 $i-2$ 级跨 2 级上来。这两类走法不重不漏（最后一步的跨度不同，绝不会数成同一种），于是把两边的方案数相加：

f[i]=f[i-1]+f[i-2]

地基要撒对： $f[0]=1$ ——「还没上台阶、原地站着」本身算一种走法（这颗 1 是所有计数的种子）； $f[1]=1$ ——到第 1 级只有「跨 1 级」一种。往后每格都是前两格之和，于是 $f$ 长成 $1,1,2,3,5,8,13,\dots$ ——正是斐波那契数列。

到第 i 级的两条来路（跨 1 级 / 跨 2 级）方案数相加；底部条带即 f[0..6]=1,1,2,3,5,8,13，斐波那契。

这套「最后一步从哪来、把各来源方案数相加」的思路是计数 DP 的通法。换个场景就成了有界计数：如果每步能跨 $1\sim K$ 级，转移就扩成一段区间求和 $f[i]=\sum_{t=1}^{K} f[i-t]$ ；如果每种「零件」还带件数上限，就是下面例题 P1077 摆花 那样的有限件计数。把这类「枚举本步取什么、累加各分支」的骨架写成中文伪代码：

# 一维计数（数楼梯 / 有界跳跃）
f[0] = 1                       # 地基：空走法算 1 种
for i = 1 to n:
    f[i] = 0
    for t = 1 to K:            # 最后一步跨 t 级（数楼梯 K=2）
        if i - t >= 0:
            f[i] += f[i - t]   # ★把 max 换成累加

# 有限件计数（第 i 种零件最多取 c 个，摆花即此形）
for i = 1 to n:
    for j = 0 to m:
        for k = 0 to min(c_i, j):
            g[i][j] += g[i-1][j-k]

本质 · 算子决定问题，骨架不动

计数 DP 和最优 DP 共用同一副状态与转移骨架——「最后一步从哪来」这套拆分毫不改变；变的只是如何聚合各来源：最优用 $\max$ 挑一个，计数用 $+$ 全加起来。两处硬改动记死： $\max\to +$ 、地基 $f[0]=1$ （空方案是唯一的起点火种）。这与 A 部分的背包综合变形是同一个道理——那里也是把背包转移的 $\max$ 换成 $+$ 、 $f[0]=1$ ，就从「最大价值」变「凑数的方案数」。

跟着算一遍

用 $n=5$ 走一遍（每步跨 1 或 2 级），把方程跑起来，手上先猜答案该是 8：

0

撒地基。

f[0]=1

（原地不动算 1 种）、

f[1]=1

（到第 1 级只能跨 1 级）。这两粒种子是整条数列的起点。

1

第 2、3 级。

f[2]=f[1]+f[0]=1+1=2

（走法

1{+}1

与

2

）；

f[3]=f[2]+f[1]=2+1=3

。

2

第 4 级。

f[4]=f[3]+f[2]=3+2=5

——从第 3 级跨 1 级来的 3 种，加上从第 2 级跨 2 级来的 2 种。

3

第 5 级。

f[5]=f[4]+f[3]=5+3=8

——正是 8 种，和开头猜的吻合。数列到此是

1,1,2,3,5,8

。

下面的演示把

f[i]

逐格累加给你看，高亮每一格由前两格（

f[i-1]

、

f[i-2]

）相加而来。改台阶数

n

，看走法数实时重算。

看走法数一格一格叠出来

跳到第 n = 5 级的走法数：f[5] = 8（f[i] = f[i−1] + f[i−2]，即斐波那契）

0

1

2

3

4

5

f

1

·

当前计算依赖来源被选转移已确定

f[0]=1,\ f[1]=1

地基：f[0]=1（原地站着算一种走法），当 n≥1 时 f[1]=1。

进度

已暂停，第 1 步，共 6 步，1 倍速

深化 · 整数划分：二维计数 dp[i][j]

数楼梯是一维计数。再上一层——整数划分：把正整数 $n$ 写成若干正整数之和（无序， $3{+}2$ 与 $2{+}3$ 算同一种），问共有多少种拆法。比如 $5$ 有 7 种： $5;\ 4{+}1;\ 3{+}2;\ 3{+}1{+}1;\ 2{+}2{+}1;\ 2{+}1{+}1{+}1;\ 1{+}1{+}1{+}1{+}1$ 。难点在「无序」：直接枚举会把 $3{+}2$ 和 $2{+}3$ 数两遍。破法是再加一维限制零件的大小，逼拆分只按「从大到小」这一种写法出现。

设 $dp[i][j]$ 表示把 $i$ 拆成若干正整数、且每个数都不超过 $j$ 的方案数。对「最大能用的零件 $j$ 」分两类：

dp[i][j]=dp[i][j-1]+dp[i-j][j]

左项 dp[i][j−1] = 完全不用 j · 右项 dp[i−j][j] = 至少用一个 j

不用 $j$ ：那能用的数就收窄到 $\le j-1$ ，方案数正是 $dp[i][j-1]$ 。至少用一个 $j$ ：先拿掉一个 $j$ ，剩下的 $i-j$ 仍可继续用 $\le j$ 的数去拆（可以再用 $j$ ），方案数是 $dp[i-j][j]$ 。两类不重不漏，相加即得。边界 $dp[0][j]=1$ （把 0 拆开只有「空拆分」一种）。答案 $dp[n][n]$ （零件不限大小）。

dp[5][3] 由两个来源相加：左邻 dp[5][2]（完全不用 3）＋上方 dp[2][3]（先扣一个 3，余 2 再拆）。二维网格逐格填。

常见陷阱 · 计数题常爆 long long，数楼梯更要高精度

方案数增长极快，随手用 $\texttt{int}$ 会溢出——计数一律先想 $\texttt{long long}$ ；题目要求取模的（如摆花 $\bmod\ 1000007$ ）则每步累加后立刻取模。更极端的是数楼梯（例题 P1255）： $n\le 5000$ 时 $f[n]$ 有上千位，连 $\texttt{long long}$ 也远远装不下，必须写高精度（用数组逐位存、逐位进位相加）。「计数 DP + 高精度」是一对常见搭档，见到「求方案数且 $n$ 很大又不取模」就该警觉。

下面的演示把整数划分的二维表 $dp[i][j]$ 逐格填出来（行 = 拆的数

i

，列 = 允许的最大零件

j

），高亮每格的左邻与上方两个来源。改

N

看方案数实时重算——

N=5

时右下角正是 7。

看整数划分的二维表填满

把 N = 5 拆成若干正整数（无序）的方案数：dp[5][5] = 7（行 = 拆的数 i，列 = 允许的最大零件 j）

0

1

2

3

4

5

拆0

拆1

拆2

拆3

拆4

拆5

1

0

·

0

·

0

·

0

·

0

·

当前计算依赖来源被选转移已确定

dp[0][j]=1,\ dp[i][0]=0\ (i>0)

地基：第 0 行都是 1；第 0 列除原点外都是 0。其余位置逐格填写。

进度

已暂停，第 1 步，共 27 步，1 倍速

例题

P1255数楼梯洛谷原生普及-

题意

一共

n

级楼梯，每步可跨 1 级或 2 级，求走到第

n

级的不同走法总数（

n\le 5000

）。

状态 · 转移

f[i]

= 到第

i

级的走法数，

f[i]=f[i-1]+f[i-2]

，

f[0]=f[1]=1

。就是斐波那契。

为什么选它

「计数 DP」与「高精度」的双料入门。递推本身一行写完，真正的门槛在

n=5000

时

f[n]

上千位、

\texttt{long long}

彻底爆掉——逼你把方案数用数组逐位相加。

陷阱 · 复杂度

必须高精度加法（逐位进位）；下标从 0 起对齐

f[0]=1

。时间

O(n\cdot L)

（

L

为位数）。

参考代码（高精度斐波那契）

C++

在洛谷打开 P1255

#include <iostream>
#include <cstring>
using namespace std;

// 数楼梯：f[i] = f[i-1] + f[i-2]，n≤5000 时结果远超 long long，必须高精度。
// 用 int 数组逆序存每一位（下标 0 = 个位），f[i] 由 f[i-1] + f[i-2] 逐位进位得到。
int n;
int a[5005][2005];               // a[i]：第 i 级走法数的高精度表示，a[i][0]=位数

void add(int *c, int *x, int *y)  // c = x + y（高精度加）
{
    int len = max(x[0], y[0]);
    for (int i = 1; i <= len; i++)
    {
        c[i] += x[i] + y[i];
        c[i + 1] += c[i] / 10;    // 进位
        c[i] %= 10;
    }
    if (c[len + 1] > 0)
    {
        len++;
    }
    c[0] = len;                   // 记录位数
}

int main()
{
    cin >> n;
    a[0][0] = 1; a[0][1] = 1;     // f[0] = 1
    a[1][0] = 1; a[1][1] = 1;     // f[1] = 1
    for (int i = 2; i <= n; i++)
    {
        add(a[i], a[i - 1], a[i - 2]);
    }

    for (int i = a[n][0]; i >= 1; i--) // 逆序输出每一位
    {
        cout << a[n][i];
    }
    cout << endl;
    return 0;
}
// TAG: 线性DP 计数 斐波那契 高精度

P1077[NOIP2012 普及组] 摆花NOIP2012 普及普及/提高-

题意

n

种花，第

i

种最多摆

a_i

盆，一共要摆恰好 $m$ 盆（同种花无区别、顺序固定），求方案数

\bmod\ 1000007

。

对应关系

有限件计数背包：把「第

i

种花取

k

盆（

0\le k\le a_i

）」当决策，

f[i][j]

= 前

i

种恰摆

j

盆的方案数，

f[0][0]=1

。

转移 · 复杂度

f[i][j]=\sum_{k=0}^{\min(a_i,j)} f[i-1][j-k]

，答案

f[n][m]

；朴素

O(nm\bar a)

，对「枚举本种取几盆」那层可用前缀和优化掉一维到

O(nm)

。

参考代码（有界计数 + 取模）

C++

在洛谷打开 P1077

#include <iostream>
using namespace std;

const int MOD = 1000007;
int n, m, a[105];
int f[105][105];                 // f[i][j]：前 i 种花恰好摆 j 盆的方案数

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    for (int j = 0; j <= m; j++)     // 0 种花只有「摆 0 盆」1 种；j>0 无解
    {
        f[0][j] = (j == 0) ? 1 : 0;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            for (int k = 0; k <= a[i] && k <= j; k++) // 第 i 种取 k 盆
            {
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % MOD;
            }
        }
    }

    cout << f[n][m] << endl;
    return 0;
}
// TAG: 线性DP 有界计数 摆花 取模

P2401不等数列洛谷原生普及+/提高

题意

把

1\sim n

填成一个排列，在相邻两数间填

<

或

>

，求恰好有

k

个

<

的排列数

\bmod\ 2015

。

为什么选它

逐个插入的排列计数范式：把最大的数

i

逐个插进已有排列，按「插入位置是否新增一个上升」建

dp[i][j]

。它与练习 P2513 逆序对数列同源，是「增量插入 + 贡献计数」的样板。

转移 · 复杂度

dp[i][j]=dp[i-1][j]\cdot(j+1)+dp[i-1][j-1]\cdot(i-1-(j-1))

：插进已有上升位（含末尾，共

j+1

处）上升数不变；插进其余位置新增一个上升。答案

dp[n][k]

，时间

O(n^2)

。

参考代码（逐个插入 · 排列计数）

C++

在洛谷打开 P2401

#include <iostream>
using namespace std;

const int MOD = 2015;
int n, k;
int f[1005][1005];               // f[i][j]：1..i 的排列中恰有 j 处 a[t]<a[t+1] 的方案数

int main()
{
    cin >> n >> k;
    f[1][0] = 1;                     // 单个数：0 处上升

    for (int i = 2; i <= n; i++)     // 把新数 i 逐个插进已有排列
    {
        for (int j = 0; j < i; j++)
        {
            // 插进原有 j 个「上升位」之一或末尾（共 j+1 处）→ 上升数不变
            long long same = (long long)f[i - 1][j] * (j + 1);
            // 插进其余位置 → 新增一个上升位 → 由 j-1 处上升转来（j=0 时无此项）
            long long grow = (j > 0) ? (long long)f[i - 1][j - 1] * (i - j) : 0;
            f[i][j] = (same + grow) % MOD;
        }
    }

    cout << f[n][k] << endl;
    return 0;
}
// TAG: 线性DP 逐个插入 排列计数 不等数列

练习

P2513[HAOI2009] 逆序对数列逐位插入 + 前缀和优化：dp[i][j] = 用 1..i 构成、恰有 j 个逆序对的排列数。把第 i 个数插进已有排列的某位会新增 0..i-1 个逆序对，故 dp[i][j] = Σ dp[i-1][j-t]（t=0..i-1），这段区间和用前缀和 O(1) 取，总复杂度 O(n·k)。与例题 P2401 同源。在洛谷打开

P1057[NOIP2008 普及组] 传球游戏环上方案计数递推：f[i][j] = 传了 i 次后球在第 j 人手里的方案数，j 只能由左右两个邻居传来 → f[i][j] = f[i-1][j-1] + f[i-1][j+1]（下标按 n 个人的环取模）。起点 f[0][1]=1，答案 f[m][1]。在洛谷打开

P2404自然数的拆分问题整数划分枚举 / 计数：把 n 拆成若干正整数之和（无序），本页二维 dp[i][j] 思路直接套用；本题还要求按字典序输出每种拆分，用 DFS 枚举「当前零件不小于上一个」即可，计数则读 dp[n][n]。在洛谷打开

计数 / 划分型

本课摘要