数楼梯

Posted on | In | | Visitors:
Words count in article: 1.2k

数楼梯

今日终于是刷到了传说中的数楼梯，这个题之前就听说过很多次，但一直没有亲手做过，今日一做，果然爆炸，太菜了T_T

洛谷P1255

上题目：

楼梯有 N 阶，上楼可以一步上一阶，也可以一步上二阶。编一个程序，计算共有多少种不同的走法。

举个栗子：

当有 4 节楼梯时，就有 1111, 112, 121, 211, 22 五种走法

1. 斐波那契数列

这个就非常有意思，可能乍一想怎么都想不到和斐波拉契数列有关，当我们的台阶数 $x$ 大于2时，我们的第一步可能走 1 个台阶或者走 2 个台阶，于是求下楼梯的方案数 $f(x)$ 就分解为了两个问题，分别求解 $f(x-1)$ 和 $f(x-2)$ ，所以我们就得到了如下式子：

看到式子就懂了，这就斐波那契数列鸭，时间复杂度为 $O(n)$

我们自然就能想到如下递推解法（当然也可以选择递归，但可能台阶数过大时反而会超时）：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int main() {
	int a[2] = { 0, 1 }, n, temp;
	cin >> n;
	for(int i = 0; i < n; i++){
		temp = a[1] + a[0];
		a[0] = a[1];
		a[1] = temp;
	}
	cout << a[1] << endl;
	return 0;
}

但是一旦楼梯的阶数一多，int 数据就会越界，因此还得上高精！我这里使用的时压位高精，其实只需要实现高精度加法就可以了，写起来还是比较方便！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
using namespace std;
#define SINGLE_LENGTH 18;
long long wayCount[5100][500] = { 0 };
void add(int index) {		// 高精度加法
	int i = 0;
	while (wayCount[index - 1][i] != 0) {
		wayCount[index][i] += (wayCount[index - 1][i] + wayCount[index - 2][i]);
		if (wayCount[index][i] > 1000000000000000000) {
			wayCount[index][i] -= 1000000000000000000;
			wayCount[index][i + 1] += 1;
		}
		i++;
	}
}
void showCount(int index) {		// 打印高精度数据
	int i = 0;
	while (wayCount[index][i] != 0)
		i++;
	i--;
	printf("%lld", wayCount[index][i]);
	i--;
	while (i >= 0) {
		printf("%018lld", wayCount[index][i]);
		i--;
	}
}
int main() {
	int n;
	cin >> n;
	wayCount[1][0] = 1, wayCount[2][0] = 2;
	for (int i = 3; i <= n; i++)
		add(i);
	showCount(n);
	return 0;
}

2. 矩阵快速幂

对于形如 $f(n) = \sum_{i = 1}^{m} f(n-i)$ 都可以构造一个如下的一个如下的一个矩阵的等式：

$\begin{bmatrix} f(n) \\ f(n-1) \\ … \\ f(n-m+2) \\ f(n-m+1) \\ \end{bmatrix} = \begin{bmatrix} a_1 & a_2 & … & a_m \\ 1 & 0 & … & 0\\ 0 & 1 & … & 0 \\ … & … & … & … \\ 0 & … & 1 & 0\\ \end{bmatrix} \begin{bmatrix} f(n - 1) \\ f(n-2) \\ … \\ f(n-m+1) \\ f(n-m) \\ \end{bmatrix}$

递推下去的话，我们就只需求解 $\begin{bmatrix} a_1 & a_2 & … & a_m \\ 1 & 0 & … & 0\\ 0 & 1 & … & 0 \\ … & … & … & … \\ 0 & … & 1 & 0\\ \end{bmatrix}$ 的 n 次方即可，对于矩阵的 n 次方，我们就能使用矩阵快速幂，就是将 n 写成二进制，然后分别乘以相应二进制位上为 1 的项即可（这里就不赘述了，需要可以自行了解~），时间复杂度为 $O(log(n))$

回到这题我们的矩阵就是 $\begin{bmatrix}
1 & 1\\
1 & 0\\
\end{bmatrix}$ ，直接看下面代码就可以了~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<string.h>
using namespace std;
void matrixMult(int a[][2], int b[][2], int c[][2]) {
	int temp[2][2];
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			temp[i][j] = b[i][0] * c[0][j] + b[i][1] * c[1][j];
		}
	}
	memcpy(a, temp, sizeof(temp));
}
int main() {
	int n, a[2][2] = { {1, 1}, {1, 0} }, result[2][2] = { {1, 0}, {0, 1} };
	cin >> n;
	while (n != 0) {
		if (n & 1) {
			matrixMult(result, result, a);
		}
		matrixMult(a, a, a);
		n >>= 1;
	}
	cout << result[0][0] << endl;
	return 0;
}

虽然时间复杂度降低了，但是仍然存在局限性，依然存在数据溢出的情况，所以还是需要上高精！但是这里需要用到高精度乘法和加法，实现起来也会更加复杂一些，还是用上面解法吧（写一遍高精度乘法也太累了吧，说不定速度还没有上面的快T_T，大佬另说~）

3. 通项公式法

我们可以根据递推公式 $f(x) = f(x-1) + f(x-2)$ 我们就可以写出特征方程 $x^2 = x + 1$， 然后一顿神奇的求解就得到了通项公式， 非常的简单（狗头），感兴趣的同学可以去看下leetcode的官方解答。

4. 一些变体

爬楼梯就有很多的变体，比如加一个限制条件：不能连续跳两个台阶，其实仔细想想还是一样的（递推公式为 $f(x) = f(x - 1) + f(x - 3)$ )

或者跳台阶有三种选择三步问题