Who's Studio.

hihoCoder#1143 - 骨牌覆盖问题·一

Word count: 153Reading time: 1 min
2016/05/10

题目

一个2*N的棋盘，用1*2的骨牌进行覆盖，一共有多少种不同的覆盖方法。
具体描述请见hihoCoder。

解题思路

动态规划，Fn = Fn-1 + Fn-2。即斐波那契数列。

时间复杂度

时间复杂度为N（可以用快速幂算法缩减到logN），空间复杂度为1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int fib(int N) {
	int f0 = 0, f1 = 1;
	for (int i = 0; i < N; i++) {
		int tmp = f1;
		f1 = (f0 + f1) % 19999997;
		f0 = tmp;
	}

	return f1;
}

int main() {
	int N = 0;
	cin >> N;

	cout << fib(N) << endl;

	return 0;
}

Author：Who Watson

Link：https://wangshenghu.github.io/2016/05/10/2016-05-10-hihocoder-gupaifugaiwenti-1/

Publish date：May 10th 2016, 3:44:00 pm

Update date：December 4th 2022, 4:42:07 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 解题思路
  3. 3. 时间复杂度
  4. 4. 代码
Total : 56
2022
2016
test
笔记 算法 hihoCoder 实习经历 项目