贴瓷砖问题——动态规划
程序员文章站
2024-03-16 09:27:52
...
题目描述:
有一块大小是 2 * n 的墙面,现在需要用2种规格的瓷砖铺满,瓷砖规格分别是 2 * 1 和 2 * 2,请计算一共有多少种铺设的方法。
输入:
输入的第一行包含一个正整数T(T<=20),表示一共有T组数据,接着是T行数据,每行包含一个正整数N(N<=30),表示墙面的大小是2行N列。
输出:
输出一共有多少种铺设的方法,每组数据的输出占一行
样例输入:
3
2
8
12
样例输出:
3
171
2731
本题用动态规划来解决比较简单:
我们先找出动态规划的递推式:
我们有两种砖可供选择,设2 * 1的砖为 A, 2 * 2的砖为 B。
当我们在最开始铺上A砖时,有两种选择:
- 竖着铺 A 砖——此时,后面的砖的铺法就是 dp[i - 1]
- 横着铺 A 砖——此时,后面的砖的铺法就是 dp[i - 2]
当我们在最开始铺上B砖时,只有一种选择:
- 即B砖占据前面四个格——则,后面的砖的铺法就是 dp[i - 2]
综上得出递推式:
dp[i] = dp[i - 1] + 2 * dp[i - 2]
由递推式写出代码:
#include<iostream>
using namespace std;
void solve(long long *dp, int n)
{
dp[1] = 1; dp[2] = 3; //初始化 n = 1 和 3 时的铺法
for (int i = 3; i <= n; i++) // 从 n = 3 开始计算
dp[i] = dp[i - 1] + 2 * dp[i - 2];
}
int main()
{
long long dp[33];
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
solve(dp, n);
cout<<dp[n]<<endl;
for (int i = 1; i <= n; i++)
cout<<dp[i]<<" ";
cout<<endl;
}
}