欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

贴瓷砖问题——动态规划

程序员文章站 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;
    }
}

相关标签: 算法设计与分析