题目描述
用 $1×2$ 和 $2×1$ 的骨牌铺满大小为 $2×n$ 的地板,请问共有多少种不同铺法。
输入格式
一个整数 $n$。
输出格式
一个整数,表示铺法数量对 $999983$ 取模后的结果。
数据范围
$1≤n≤10000$
输入样例
6
输出样例
13
简单介绍一下思路
在$2*n$的格子里
如果$n$为$0$,则必然为$0$种
如果$n$为$1$,则有$1$种,竖着放一个$1*2$的骨牌
如果$n$为$2$,则有$2$种:
竖着放两个$1*2$的骨牌
横着放两个$2*1$的骨牌
当$n>2$的时候,便有两种选择:
$①$:在前一步的基础上再竖着放一个$1*2$的骨牌
$②$:在前两步的基础上再横着着放两个$2*1$的骨牌
因此推导出$opt[i] = opt[i-1] + opt[i-2]$ 两种情况之和
前面的题解说像走楼梯,的确也是这样子
代码
#include <bits/stdc++.h>
using namespace std;
int n;
int opt[10010] = {0,1,2};
int main(){
cin >> n;
for(int i = 3; i <= n; i++){
opt[i] = (opt[i-1] + opt[i-2]) % 999983;
}
cout << opt[n] << endl;
return 0;
}
这道水题能快速入门$dp$,作为我下一个题解的铺垫click here
我是新手qwq
无耻求赞