基础 DP

斐波那契数列

斐波那契数列是形如 ${1, 1, 2, 3, 5, 8, \dots}$ 的数列，求数列的第 $n$ 项。

分析

$f [n]$ ：数列的第 $n$ 项。

f [n] = {\begin{cases} 1 & n = 1, 2 \\ f [n - 1] + f [n - 2] & n \geq 3 \end{cases}

cpp

f[1] = f[2] = 1;
for (int i = 3; i <= n; i ++)
	f[i] = f[i - 1] + f[i - 2];

汉诺塔问题

汉诺塔由 $n$ 个不同的盘子和 $3$ 根杆子组成，从左到右为 $a$ 杆， $b$ 杆， $c$ 杆。初始时， $n$ 个盘子从大到小叠在 $a$ 杆上。

现在，按以下规则将 $n$ 个盘子从 $a$ 杆移到 $c$ 杆。

一次只能动一个盘子；
盘子只能放在杆上；
大盘子不能叠在小盘子上。

求移动盘子的最少次数。

分析

$f [n]$ ：将 $n$ 个盘子从一杆移至另一杆，所需的最少移动次数。

将 $n$ 个盘子从 $a$ 杆移到 $c$ 杆，需要以下 $3$ 步：

将 $a$ 杆的 $n -$ $1$ 个盘子移至 $b$ 杆（共 $f [n -$ $1]$ 次）；
将 $a$ 杆的最后一个盘子移至 $c$ 杆（共 $1$ 次）；
将 $b$ 杆的 $n -$ $1$ 个盘子移至 $c$ 杆（共 $f [n -$ $1]$ 次）。

f [n] = {\begin{cases} 1 & n = 1 \\ 2 \cdot f [n - 1] + 1 & n \geq 2 \end{cases}

cpp

f[1] = 1;
for (int i = 2; i <= n; i ++)
	f[i] = 2 * f[i - 1] + 1;

骨牌问题

用若干 $1 \times 2$ 的骨牌铺满 $2 \times n$ 的方格。如图为 $n =$ $3$ 时的所有铺法。

求任意 $n$ 对应的方法总数。

分析

$f [n]$ ： $n$ 对应的方法总数。

若第一个骨牌竖放在左边，则剩余 $2 \times (n -$ $1)$ 个空方格，铺法数为 $f [n -$ $1]$ ；
若第一个骨牌横放在左上角，为了不留空，第二个骨牌必须横放在其正下方。剩余 $2 \times (n -$ $2)$ 个空方格，铺法数为 $f [n -$ $2]$ 。

f [n] = {\begin{cases} 1 & n = 1 \\ 2 & n = 2 \\ f [n - 1] + f [n - 2] & n \geq 3 \end{cases}

状态转移方程和斐波那契数列一致。

平面分割问题

平面上有 $n$ 条闭曲线，每 $2$ 条恰好交于 $2$ 点，且每 $3$ 条不交于同一点。求平面被分割成的区域个数。

分析

$a [n]$ ： $n$ 条封闭曲线分割成的区域个数。

由上图可得：

\begin{array}{r} a [1] = 2 \\ a [2] - a [1] = 2 \\ a [3] - a [2] = 4 \\ a [4] - a [3] = 6 \end{array}

即

a [n] = {\begin{cases} 2 & n = 1 \\ a [n - 1] + 2 (n - 1) & n \geq 2 \end{cases}

正确性证明：

新增一条曲线时，每与一条已有曲线相交一次，就增加一个区域。而新增的第 $n$ 条曲线与已有的 $n -$ $1$ 条曲线各有 $2$ 个交点。

$∴$ 新增区域数 $=$ 新增交点数 $=$ $2 \cdot (n -$ $1)$ 。

$∴$ 现有区域个数 $a [n] =$ 原有区域个数 $+$ 新增区域个数 $=$ $a [n -$ $1] +$ $2 (n -$ $1)$ 。

cpp

a[1] = 2;
for (int i = 2; i <= n; i ++)
	a[i] = a[i - 1] + 2 * (n - 1);

最长上升子序列 (LIS)

求序列 $A$ （长度 $n$ ）的最长上升子序列 $LIS (A)$ 的长度。

例： $A =$ ${2, 3, 6, 4, 5, 1}$ , $LIS (A) =$ ${2, 3, 4, 5}$ （长度 $4$ ）。

分析

$f [i]$ ： $LIS (A_{1 \dots i})$ 的长度。

枚举 $j =$ $1 \dots i -$ $1$ ：

若 $A_{j} < A_{i}$ ，则 $A_{i}$ 可以接在 $LIS (A_{1 \dots j})$ 后面，形成的上升子序列长度为 $f [j] +$ $1$ ；
若 $A_{j} \geq A_{i}$ ， $A_{j}$ 对 $f [i]$ 没有贡献，直接跳过。

f [i] = max_{j < i, A_{j} < A_{i}} (f [j] + 1)

问题的解是 $f [n]$ 。

cpp

for (int i = 1; i <= n; i ++) {
	f[i] = 1;
	for (int j = 1; j < i; j ++)
		if (a[j] < a[i])
			f[i] = max(f[i], f[j] + 1);
}

单调栈优化

扫描每一个数，有策略地将其加入单调栈，使得栈的内容始终是当前的最长上升子序列。

举例来说，假设当前单调栈内有 ${2, 3, 6}$ ，而扫描到 $4$ 。根据贪心原理，将 $6$ 替换为 $4$ 更有利于后续上升子序列的扩展。

当扫描到 $a [i]$ ：

若 $a [i]$ 大于栈尾，则直接将其入栈；
否则在栈中二分查找第一个 $\geq a [i]$ 的数，将其替换为 $a [i]$ 。

最终栈的长度即为 LIS 的长度。时间复杂度为 $O (n \log n)$ 。

cpp

vector<int> s;
s.push_back(a[1]);
for (int i = 2; i <= n; i ++) {
	if (a[i] > s.back())
		s.push_back(a[i]);
	else
		*lower_bound(s.begin(), s.end(), a[i]) = a[i];
}

最长公共子序列 (LCS)

求序列 $A$ （长度 $n$ ）和序列 $b$ （长度 $m$ ）的最长公共子序列 $LCS (A,$ $B)$ 的长度。

例： $A =$ freeze, $B =$ refeze, $LCS (A,$ $B) =$ reeze（长度 $5$ ）。

分析

$f [i,$ $j]$ ： $LCS (A_{1 \dots i},$ $B_{1 \dots j})$ 的长度。

枚举 $i =$ $1 \dots n$ ：
- 枚举 $j =$ $1 \dots m$ ：
  - 首先继承最优子状态： $f [i,$ $j] =$ $max {f [i - 1, j], f [i, j - 1]}$ ；
  - 若 $A_{i} =$ $B_{j}$ ，则 $A_{i}$ 可以接在 $LCS (A_{1 \dots i - 1},$ $B_{1 \dots j - 1})$ 之后，形成的公共序列长度为 $f [i -$ $1,$ $j -$ $1] +$ $1$ 。

f [i, j] = max {\begin{aligned} f [i - 1, j] \\ f [i, j - 1] \\ f [i - 1, j - 1] + 1, & A_{i} = B_{j} \end{aligned}

问题的解是 $f [n] [m]$ 。

cpp

for (int i = 1; i <= n; i ++) {
	for (int j = 1; j <= m; j ++) {
		f[i][j] = max(f[i - 1][j], f[i][j - 1]);
		if (a[i] == b[j])
			f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
	}
}

数字金字塔

三角矩阵 $A$ 有 $n$ 行，第 $i$ 行有 $i$ 列。从第一行第一列出发，每次可以移动到下一行相邻的两个数字。到达底部时，经过的数字之和最大为多少？

13[@n=" $13$ ", @normal]
8[@n=" $8$ ", @normal]
11[@n=" $11$ ", @normal]
7[@n=" $7$ ", @normal]
12[@n=" $12$ ", @normal]
26[@n=" $26$ ", @normal]
9[@n=" $9$ ", @normal]
15[@n=" $15$ ", @normal]
14[@n=" $14$ ", @normal]
6[@n=" $6$ ", @normal]
13 -> 8
13 -> 11
8 -> 26
8 -> 7
11 -> 7
11 -> 12
26 -> 9
26 -> 15
7 -> 15
7 -> 14
12 -> 14
12 -> 6

此例中，最优路径为 $13 \to 8 \to 26 \to 15$ ，最大值为 $62$ 。

分析

$(i,$ $j)$ ：第 $i$ 行第 $j$ 列的数字。

$f [i,$ $j]$ ：走到 $(i,$ $j)$ 时，经过的数字之和的最大值。

逆推法：要走到 $(i,$ $j)$ ，则上一步只能在 $(i -$ $1,$ $j -$ $1)$ 或 $(i -$ $1,$ $j)$ 。

f [i, j] = (i, j) + max {\begin{aligned} f [i - 1, j - 1] \\ f [i - 1, j] \end{aligned}

注意：当 $j =$ $1$ 或 $j =$ $i$ 时， $f [i -$ $1,$ $j -$ $1]$ 和 $f [i -$ $1,$ $j]$ 会越界。故将 $f$ 数组初始化为 $-$ $\infty$ ，使越界的元素在 $max$ 比较中被自动淘汰。

问题的解是

max_{1 \leq i \leq n} {f [n, i]}

cpp

memset(f, 0x80, sizeof f);
f[1][1] = 1;
for (int i = 2; i <= n; i ++) {
	for (int j = 1; j <= i; j ++) {
		cin >> f[i][j];
		f[i][j] += max(f[i - 1][j - 1], f[i - 1][j]);
	}
}
ans = 0;
for (int i = 1; i <= n; i ++)
	ans = max(ans, f[n][i]);

数字矩阵

有 $n$ 行 $m$ 列的数字矩阵 $A$ 。从左上角出发，每次只能向下或向右走一步。到右下角时，经过的数字之和最大为多少？

@neato;
n1 [@(0,0), @n=" $3$ "];
n2 [@(0.8,0), @n=" $8$ "];
n3 [@(1.6,0), @n=" $4$ "];
n4 [@(2.4,0), @n=" $2$ "];
n5 [@(0,0.8), @n=" $5$ "];
n6 [@(0.8,0.8), @n=" $11$ ", @normal];
n7 [@(1.6,0.8), @n=" $12$ ", @normal];
n8 [@(2.4,0.8), @n=" $9$ "];
n9 [@(0,1.6), @n=" $3$ "];
n10 [@(0.8,1.6), @n=" $8$ "];
n11 [@(1.6,1.6), @n=" $4$ "];
n12 [@(2.4,1.6), @n=" $2$ "];
n1 -> n2 -> n3 -> n4
n5 -> n6 -> n7 -> n8
n9 -> n10 -> n11 -> n12
n9 -> n5 -> n1
n10 -> n6 -> n2
n11 -> n7 -> n3
n12 -> n8 -> n4

此例中，最优路径为 $3 \to 8 \to 11 \to 12 \to 9 \to 2$ ，最大值为 $61$ 。

分析

$(i,$ $j)$ ：第 $i$ 行第 $j$ 列的数字。

$f [i,$ $j]$ ：走到 $(i,$ $j)$ 时，经过的数字之和的最大值。

逆推法：由于只能向左走或向下走，要走到 $(i,$ $j)$ ，上一步只能在 $(i -$ $1,$ $j)$ 或 $(i,$ $j -$ $1)$ 。

f [i, j] = (i, j) + max {\begin{aligned} f [i - 1, j] \\ f [i, j - 1] \end{aligned}

注意：当 $i =$ $1$ 或 $j =$ $1$ 时， $f [i -$ $1,$ $j]$ 和 $f [i,$ $j -$ $1]$ 会越界。 $f$ 数组须初始化为 $-$ $\infty$ 。

cpp

memset(f, 0x80, sizeof f);
for (int i = 1; i <= n; i ++) {
	for (int j = 1; j <= m; j ++) {
		cin >> f[i][j];
		if (!(i == 1 && j == 1))
			f[i][j] += max(f[i-1][j], f[i][j - 1]);
	}
}

前缀和

前缀和是一种重要的预处理技巧，能大幅降低查询数列的 连续元素之和 的时间复杂度。

预处理

数列 $A$ 有 $n$ 个元素。

$f [i]$ : $A_{1}$ 到 $A_{i}$ 的和。

f [i] = f [i - 1] + A_{i}

时间复杂度： $O (n)$ 。

cpp

for (int i = 1; i <= n; i ++)
	f[i] = f[i - 1] + a[i];

查询

$g [i,$ $j]$ ： $A_{i}$ 到 $A_{j}$ 的和。

g [i, j] = f [j] - f [i - 1]

单次查询的时间复杂度： $O (1)$ 。

cpp

// sum of a[i ... j]
int g(int i, int j) {
	return f[j] - f[i - 1];
}

二维前缀和

预处理

矩阵 $A$ 有 $n$ 行 $m$ 列。

$(i,$ $j)$ ：第 $i$ 行第 $j$ 列的数字。

$f [i,$ $j]$ ：以 $(1,$ $1)$ 为左上角，以 $(i,$ $j)$ 为右下角的矩阵的元素和。

f [i, j] = f [i - 1, j] + f [i, j - 1] - f [i - 1, j - 1] + (i, j)

@neato;
#w=1; #2w=2; #3w=3; #4w=4; #cw=0;
#h=0.4; #2h=0.8; #3h=1.2; #4h=1.6; #ch=2.0;
#siz = width=#w, height=#h;
node [
shape=box,
#siz
fixedsize=true,
style=filled,
];
node [@n0]
c1[@(#w,#ch), @n=" $y =$  $1$ ", @plain]
c3[@(#4w,#ch), @n=" $y =$  $j$ ", @plain]
c4[@(#cw,#4h), @n=" $x =$  $1$ ", @plain]
c6[@(#cw,#h), @n=" $x =$  $i$ ", @plain]
a11[@(#w,#4h), @n=" $1,$  $1$ ", @green, #siz]
a12[@(#2w,#4h), @green]
a13[@(#3w,#4h), @green]
a14[@(#4w,#4h), @yellow]
a21[@(#w,#3h), @green]
a22[@(#2w,#3h), @green]
a23[@(#3w,#3h), @green]
a24[@(#4w,#3h), @yellow]
a31[@(#w,#2h), @green]
a32[@(#2w,#2h), @green]
a33[@(#3w,#2h), @n=" $i -$  $1,$  $j -$  $1$ ", @green, #siz]
a34[@(#4w,#2h), @n=" $i -$  $1,$  $j$ ", @yellow, #siz]
a41[@(#w,#h), @blue]
a42[@(#2w,#h), @blue]
a43[@(#3w,#h), @n=" $i,$  $j -$  $1$ ", @blue, #siz]
a44[@(#4w,#h), @n=" $i,$  $j$ ", #siz]

时间复杂度： $O (n m)$ 。

cpp

f[0][0] = 0;
for (int i = 1; i <= n; i ++)
	for (int j = 1; j <= m; j ++)
		f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];

查询

$g [x_{1},$ $y_{1},$ $x_{2},$ $y_{2}]$ ：以 $(x_{1},$ $y_{1})$ 为左上角，以 $(x_{2},$ $y_{2})$ 为右下角的矩阵的元素和。

g [x_{1}, y_{1}, x_{2}, y_{2}] = f [x_{2}, y_{2}] - f [x_{1} - 1, y_{2}] - f [x_{2}, y_{1} - 1] + f [x_{1} - 1, y_{1} - 1]

@neato;
#w=1; #2w=2; #3w=3; #4w=4; #cw=0;
#h=0.4; #2h=0.8; #3h=1.2; #4h=1.6; #ch=2.0;
#siz = width=#w, height=#h;
node [
shape=box,
#siz,
fixedsize=true,
style=filled,
];
node [@n0]
c1[@(#w,#ch), @n=" $y =$  $1$ ", @plain]
c2[@(#3w,#ch), @n=" $y =$  $y_{1}$ ", @plain]
c3[@(#4w,#ch), @n=" $y =$  $y_{2}$ ", @plain]
c4[@(#cw,#4h), @n=" $x =$  $1$ ", @plain]
c5[@(#cw,#2h), @n=" $x =$  $x_{1}$ ", @plain]
c6[@(#cw,#h), @n=" $x =$  $x_{2}$ ", @plain]
a11[@(#w,#4h), @n=" $1,$  $1$ ", @green, #siz]
a12[@(#2w,#4h), @green]
a13[@(#3w,#4h), @yellow]
a14[@(#4w,#4h), @yellow]
a21[@(#w,#3h), @green]
a22[@(#2w,#3h), @green]
a23[@(#3w,#3h), @yellow]
a24[@(#4w,#3h), @yellow, @n=" $x_{1} -$  $1,$  $y_{2}$ ", #siz]
a31[@(#w,#2h), @blue]
a32[@(#2w,#2h), @blue]
a33[@(#3w,#2h), @n=" $x_{1},$  $y_{1}$ ", #siz]
a34[@(#4w,#2h)]
a41[@(#w,#h), @blue]
a42[@(#2w,#h), @blue, @n=" $x_{2},$  $y_{1} -$  $1$ ", #siz]
a43[@(#3w,#h)]
a44[@(#4w,#h), @n=" $x_{2},$  $y_{2}$ ", #siz]

单次查询的时间复杂度： $O (1)$ 。

cpp

int g(int x1, int y1, int x2, int y2) {
	return f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1];
}

差分

差分是前缀和的逆运算，能大幅降低区间修改的时间复杂度。

预处理

数列 $A$ 有 $n$ 个元素。

令 $f [i] =$ $A_{i} -$ $A_{i - 1}$ . $f$ 为差分数列。

时间复杂度： $O (n)$ 。

cpp

for (int i = 1; i <= n; i ++)
	f[i] = a[i] - a[i - 1];

区间修改

当给 $A_{l} \dots A_{r}$ 统一加上 $x$ 时， $f [l]$ 增加了 $x$ ， $f [r +$ $1]$ 减少了 $x$ , $f$ 数列中其余元素不变。

因此可以每次只修改 $f [l]$ 和 $f [r +$ $1]$ ，最后通过差分数列 $f$ 还原出 $A$ 。

单次修改的时间复杂度： $O (1)$ 。

cpp

void add(int l, int r, int x) { // add x to A[l ... r]
	f[l] += x, f[r + 1] -= x;
}

void restore() {
	for(int i = 1; i <= n; i ++)
		a[i] = a[i - 1] + f[i];
}

同余

组合数学

数值分析

多项式

圆锥曲线

斐波那契数列

汉诺塔问题

骨牌问题

平面分割问题

最长上升子序列 (LIS)

最长公共子序列 (LCS)

数字金字塔

数字矩阵

前缀和

预处理

查询

二维前缀和

预处理

查询

差分

预处理

区间修改

基础 DP

斐波那契数列 ​

汉诺塔问题 ​

骨牌问题 ​

平面分割问题 ​

最长上升子序列 (LIS) ​

最长公共子序列 (LCS) ​

数字金字塔 ​

数字矩阵 ​

前缀和 ​

预处理 ​

查询 ​

二维前缀和 ​

预处理 ​

查询 ​

差分 ​

预处理 ​

区间修改 ​

斐波那契数列

汉诺塔问题

骨牌问题

平面分割问题

最长上升子序列 (LIS)

最长公共子序列 (LCS)

数字金字塔

数字矩阵

前缀和

预处理

查询

二维前缀和

预处理

查询

差分

预处理

区间修改