斐波那契数列

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

分析

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

$$f[n]=\{\begin{array}{ll}1& n=1,2\\ f[n-1]+f[n-2]& n\ge 3\end{array}$$

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$ 杆。

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

求移动盘子的最少次数。

分析

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

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

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

$$f[n]=\{\begin{array}{ll}1& n=1\\ 2\cdot f[n-1]+1& n\ge 2\end{array}$$

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{array}{ll}1& n=1\\ 2& n=2\\ f[n-1]+f[n-2]& n\ge 3\end{array}$$

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

平面分割问题

平面上有 $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{array}{ll}2& n=1\\ a[n-1]+2(n-1)& n\ge 2\end{array}$$

正确性证明：

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

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

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

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

最长上升子序列 (LIS)

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

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

分析

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

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

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

$$f[i]=\underset{j<i,A_j<A_i}{max}(f[j]+1)$$

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

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]$ 大于栈尾，则直接将其入栈；
• 否则在栈中二分查找第一个 $\ge a[i]$ 的数，将其替换为 $a[i]$。

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

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$）的最长公共子序列 $\mathrm{LCS}(A,B)$ 的长度。

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

分析

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

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

$$f[i,j]=max\{\begin{array}{rl}& f[i-1,j]\\ & f[i,j-1]\\ & f[i-1,j-1]+1,& A_i=B_j\end{array}$$

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

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{array}{rl}& f[i-1,j-1]\\ & f[i-1,j]\end{array}$$

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

问题的解是

$$\underset{1\le i\le n}{max}\{f[n,i]\}$$

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{array}{rl}& f[i-1,j]\\ & f[i,j-1]\end{array}$$

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

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)$。

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)$。

// 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(nm)$。

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)$。

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)$。

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

区间修改

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

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

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

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];
}