C++ 多米诺骨牌和三米诺骨牌铺设

2025年2月11日 | 阅读 12 分钟

多米诺骨牌和三格骨牌铺设问题是组合数学和计算机科学中一个迷人且经典的问题。它涉及到在没有重叠或间隙的情况下，确定使用多米诺骨牌和三格骨牌完全覆盖 2×n 板的方法数量。这个问题不仅能洞察算法设计，还能作为动态规划的一个实际示例，动态规划是一种通过将问题分解为更简单的子问题来有效解决问题的方法。

多米诺骨牌和三格骨牌

多米诺骨牌：多米诺骨牌是一种覆盖 两个格子的矩形瓷砖。它可以水平或垂直放置在板上。

三格骨牌：三格骨牌是一种覆盖三个格子的瓷砖。三格骨牌有不同的类型，但在本问题中，我们考虑两种主要形式：直线三格骨牌（实际上被视为三块排成一行的多米诺骨牌）和 L 形三格骨牌（覆盖呈 L 形的三个格子）。

给定一个 2×n 板，目标是计算使用多米诺骨牌和三格骨牌的组合来完全铺设该板的不同方法数量。此问题可以被视为排列瓷砖，使整个板被瓷砖完全覆盖一次，而不会留下任何格子未覆盖或瓷砖重叠。

方法一：动态规划方法

动态规划 (DP) 是一种强大的技术，通过将复杂问题分解为更简单的子问题，对每个子问题只求解一次，并存储它们的解来解决复杂问题。此方法通过避免冗余计算来显著提高效率。以下是动态规划应用于多米诺骨牌和三格骨牌铺设问题的详细解释。

动态规划基于两个关键原则：

最优子结构：如果一个问题的最优解包含其子问题的最优解，则该问题具有最优子结构。

重叠子问题：如果一个问题可以分解为多次重复使用的子问题，则该问题具有重叠子问题。

多米诺骨牌和三格骨牌铺设问题完美契合这些原则，因为对 2×n 板进行铺设可以分解为更小的铺设问题，并且许多子问题是重叠的。

程序

 
#include <iostream>
#include <vector>

using namespace std;
// Function to count the number of ways to tile a 2xn board using dynamic programming
int countTilingWays(int n) {
    // Handle base cases explicitly
    if (n < 0) return 0;
    if (n == 0) return 1;
    if (n == 1) return 1;
    if (n == 2) return 2;    
    // Create a vector to store the number of ways to tile boards of length 0 to n
    vector<int> dp(n + 1, 0);
    dp[0] = 1;  // Base case: One way to tile an empty board
    dp[1] = 1;  // Base case: One way to tile a 2x1 board
    dp[2] = 2;  // Base case: Two ways to tile a 2x2 board   
    // Fill the dp array using the recursive formula
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i-1] + dp[i-2] + 2 * dp[i-3];
        // Display intermediate steps for better understanding
        cout << "dp[" << i << "] = dp[" << i-1 << "] + dp[" << i-2 << "] + 2 * dp[" << i-3 << "]" << endl;
        cout << "       = " << dp[i-1] << " + " << dp[i-2] << " + 2 * " << dp[i-3] << endl;
        cout << "       = " << dp[i] << endl;
    }  
    return dp[n];
}
int main() {
    int n;    
    // Input validation
    do {
        cout << "Enter the length of the board (n must be a non-negative integer): ";
        cin >> n;
        if (n < 0) {
            cout << "Invalid input. Please enter a non-negative integer." << endl;
        }
    } while (n < 0);
    // Count the number of ways to tile the board and display the result
    int result = countTilingWays(n);
    cout << "Number of ways to tile a 2x" << n << " board: " << result << endl;  
    // Display the filled dp array
    cout << "DP array contents:" << endl;
    for (int i = 0; i <= n; ++i) {
        cout << "dp[" << i << "] = " << countTilingWays(i) << endl;
    }    
    return 0;
}

输出

 
Enter the length of the board (n must be a non-negative integer): 8
dp[3] = dp[2] + dp[1] + 2 * dp[0]
       = 2 + 1 + 2 * 1
       = 5
dp[4] = dp[3] + dp[2] + 2 * dp[1]
       = 5 + 2 + 2 * 1
       = 9
dp[5] = dp[4] + dp[3] + 2 * dp[2]
       = 9 + 5 + 2 * 2
       = 18
dp[6] = dp[5] + dp[4] + 2 * dp[3]
       = 18 + 9 + 2 * 5
       = 37
dp[7] = dp[6] + dp[5] + 2 * dp[4]
       = 37 + 18 + 2 * 9
       = 73
dp[8] = dp[7] + dp[6] + 2 * dp[5]
       = 73 + 37 + 2 * 18
       = 146
Number of ways to tile a 2x8 board: 146
DP array contents:
dp[0] = 1
dp[1] = 1
dp[2] = 2
dp[3] = dp[3] = dp[2] + dp[1] + 2 * dp[0]
       = 2 + 1 + 2 * 1
       = 5
5
dp[4] = dp[3] = dp[2] + dp[1] + 2 * dp[0]
       = 2 + 1 + 2 * 1
       = 5
dp[4] = dp[3] + dp[2] + 2 * dp[1]
       = 5 + 2 + 2 * 1
       = 9
9
dp[5] = dp[3] = dp[2] + dp[1] + 2 * dp[0]
       = 2 + 1 + 2 * 1
       = 5
dp[4] = dp[3] + dp[2] + 2 * dp[1]
       = 5 + 2 + 2 * 1
       = 9
dp[5] = dp[4] + dp[3] + 2 * dp[2]
       = 9 + 5 + 2 * 2
       = 18
18
dp[6] = dp[3] = dp[2] + dp[1] + 2 * dp[0]
       = 2 + 1 + 2 * 1
       = 5
dp[4] = dp[3] + dp[2] + 2 * dp[1]
       = 5 + 2 + 2 * 1
       = 9
dp[5] = dp[4] + dp[3] + 2 * dp[2]
       = 9 + 5 + 2 * 2
       = 18
dp[6] = dp[5] + dp[4] + 2 * dp[3]
       = 18 + 9 + 2 * 5
       = 37
37
dp[7] = dp[3] = dp[2] + dp[1] + 2 * dp[0]
       = 2 + 1 + 2 * 1
       = 5
dp[4] = dp[3] + dp[2] + 2 * dp[1]
       = 5 + 2 + 2 * 1
       = 9
dp[5] = dp[4] + dp[3] + 2 * dp[2]
       = 9 + 5 + 2 * 2
       = 18
dp[6] = dp[5] + dp[4] + 2 * dp[3]
       = 18 + 9 + 2 * 5
       = 37
dp[7] = dp[6] + dp[5] + 2 * dp[4]
       = 37 + 18 + 2 * 9
       = 73
73
dp[8] = dp[3] = dp[2] + dp[1] + 2 * dp[0]
       = 2 + 1 + 2 * 1
       = 5
dp[4] = dp[3] + dp[2] + 2 * dp[1]
       = 5 + 2 + 2 * 1
       = 9
dp[5] = dp[4] + dp[3] + 2 * dp[2]
       = 9 + 5 + 2 * 2
       = 18
dp[6] = dp[5] + dp[4] + 2 * dp[3]
       = 18 + 9 + 2 * 5
       = 37
dp[7] = dp[6] + dp[5] + 2 * dp[4]
       = 37 + 18 + 2 * 9
       = 73
dp[8] = dp[7] + dp[6] + 2 * dp[5]
       = 73 + 37 + 2 * 18
       = 146
146

说明

提供的 C++ 代码使用动态规划来解决多米诺骨牌和三格骨牌铺设问题，这是一种 处理此类组合问题的有效方法。在这里，目标是确定使用多米诺骨牌和三格骨牌完全铺设 2×n 板而不存在任何 重叠或间隙的方法数量。

输入验证

程序从输入验证开始，确保用户为板的长度 n 输入一个非负整数。此步骤涉及 do-while 循环，该循环 反复提示用户输入，直到提供有效值为止。这对于确保算法在其 定义约束范围内运行至关重要，并可防止因无效输入而可能产生的错误。

动态规划数组初始化

获得有效的 n 后，程序会初始化一个 vector dp 来存储从 0 到 n 的板铺设方法的数量。此数组是 动态规划方法的核心，因为它存储了子问题的解，然后这些解用于构建主问题的解。

处理基本情况

基本情况已明确处理：

dp[0]=1：铺设一个空板只有一种方法，即什么都不做。

dp[1]=1：铺设一个 2×1 的板只有一种方法，即放置一个垂直的多米诺骨牌。

dp[2]=2：铺设一个 2×2 的板有两种方法：要么放置两个垂直的多米诺骨牌，要么放置两个水平的多米诺骨牌。

这些基本情况至关重要，因为它们提供了开始递归计算更大 n 值所需的初始值。

递归计算

动态规划解决方案的核心在于填充 dp 数组（对于 n≥3）的循环。对于从 3 到 n 的每个值 i，程序使用以下公式计算 dp[i]：dp[i]=dp[i-1]+dp[i-2]+2×dp[i-3]

此公式考虑了板上最后一个瓷砖的三种可能配置：一个垂直的多米诺骨牌覆盖最后一列，留下一个 2×(i-1) 的板。

两个水平的多米诺骨牌覆盖最后两列，留下一个 2×(i-2) 的板。一个 L 形三格骨牌覆盖最后三列，可以有两种不同的方向放置，留下一个 2×(i-3) 的板。

每次迭代的中间步骤和计算会打印到控制台以便更好地理解。这种详细的分解有助于可视化 dp 数组中的值如何得出，并为动态规划过程提供了透明性。

显示结果

循环完成后，程序会输出最终结果，即铺设 2×n 板的方法数量。此外，程序还会打印 dp 数组的内容，显示从 0 到 n 的所有长度的板的铺设方法数量。这对于调试和验证计算是否正确很有用。

复杂度分析

时间复杂度

提供的动态规划解决方案的时间复杂度可以根据函数 countTilingWays 中执行的操作数量进行分析。

初始化和输入验证

初始化 dp 数组和设置基本情况涉及常量工作量。输入验证涉及一个循环，该循环一直运行直到提供有效输入，但这不依赖于 n，因此在分析主算法的上下文中可以视为 O(1)。

填充 DP 数组

主循环从 3 运行到 n。在每次迭代中，都会执行常量工作量来使用递归公式计算 dp[i]：dp[i]=dp[i-1]+dp[i-2]+2×dp[i-3]

此循环运行 n-2 次，简化为 O(n)，因为随着 n 的增长，减去一个常数变得可以忽略不计。

因此，countTilingWays 函数的总体时间复杂度为 O(n)。

空间复杂度

算法的空间复杂度由存储 dp 数组所需的空间决定。

DP 数组存储

dp 数组用于存储从 0 到 n 的板铺设方法的数量。dp 数组的大小为 n+1，这意味着它需要 O(n) 的空间。

附加变量

该算法使用几个额外的变量（例如，n、循环计数器），但这些变量只需要 O(1) 的常量空间。

因此，countTilingWays 函数的总体空间复杂度为 O(n)。

方法二：矩阵幂运算

在此方法中，我们使用矩阵幂运算来表示问题，以找到铺设 2×n 板的方法数量。当 n 很大时，此方法特别有用，因为它将时间复杂度从动态规划的 O(n) 降低到 O(logn)。

程序

 
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7; // Modulo to handle large numbers
// Define a 3x3 matrix structure
struct Matrix {
    vector<vector<long long>> mat;
    int rows, cols;
    // Constructor to initialize matrix of size rows x cols with zeros
    Matrix(int r, int c) : rows(r), cols(c) {
        mat.resize(rows, vector<long long>(cols, 0));
    }
    // Function to perform matrix multiplication
    Matrix operator*(const Matrix& other) {
        Matrix result(rows, other.cols);
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < other.cols; ++j) {
                for (int k = 0; k < cols; ++k) {
                    result.mat[i][j] = (result.mat[i][j] + mat[i][k] * other.mat[k][j]) % MOD;
                }
            }
        }
        return result;
    }
};
// Function to perform matrix exponentiation
Matrix matrixExponentiation(Matrix base, int exp) {
    Matrix result(base.rows, base.cols);
    // Initialize result as identity matrix
    for (int i = 0; i < base.rows; ++i) {
        result.mat[i][i] = 1;
    }
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = result * base;
        }
        base = base * base;
        exp /= 2;
    }
    return result;
}
// Function to calculate the number of ways to tile a 2xn board using matrix exponentiation
long long countTilingWays(int n) {
    // Base cases
    if (n == 0) return 1; // Empty board
    if (n == 1) return 1; // 2x1 board
    if (n == 2) return 2; // 2x2 board
    // Create transformation matrix T
    Matrix T(3, 3);
    T.mat = {{1, 1, 2}, {1, 0, 0}, {0, 1, 0}};
    // Calculate T^(n-2)
    Matrix result = matrixExponentiation(T, n - 2);
    // The number of ways to tile a 2xn board is given by T^(n-2)[0][0] * 2 + T^(n-2)[0][1] * 1 + T^(n-2)[0][2] * 2
    long long ways = (result.mat[0][0] * 2 + result.mat[0][1] * 1 + result.mat[0][2] * 2) % MOD;
    return ways;
}
int main() {
    // Welcome message and instructions for the user
    cout << "Welcome to the Domino and Tromino Tiling Problem Solver!" << endl;
    cout << "This program calculates the number of ways to tile a 2xn board using dominoes and trominoes." << endl;
    // Get valid input from the user
    int n;
    cout << "Enter the length of the board (n): ";
    cin >> n;
    // Calculate the number of ways to tile the board
    long long result = countTilingWays(n);
    // Display the result
    cout << "Number of ways to tile a 2x" << n << " board: " << result << endl;
    return 0;
}

输出

 
Welcome to the Domino and Tromino Tiling Problem Solver!
This program calculates the number of ways to tile a 2xn board using dominoes and trominoes.
Enter the length of the board (n): 2
Number of ways to tile a 2x2 board: 2

说明

提供的代码使用矩阵幂运算来有效地解决 2×n 板的多米诺骨牌和三格骨牌铺设问题。此方法利用线性代数和矩阵乘法的性质以 对数时间计算解决方案，这对于大的 n 尤其有用。

矩阵结构

Matrix 结构定义了一个具有行和列的矩阵，并提供了一个构造函数来初始化一个填充有零的矩阵。

operator* 函数实现了矩阵乘法，这对于矩阵幂运算至关重要。

矩阵幂运算

matrixExponentiation 函数使用 平方求幂方法将矩阵提升到指数幂。此方法将时间复杂度降低到 O(logn)。

它从单位矩阵开始，单位矩阵在矩阵运算中作为 乘法单位元。

变换矩阵

变换矩阵 T 捕获了递推关系：T(n)=T(n-1)+T(n-2)+2×T(n-3)

处理大数

为防止溢出并遵守组合问题中的典型约束，所有计算均 模 10^9+7进行。

用户交互

main 函数提示用户输入板的长度 n，调用 countTilingWays 来计算结果，然后显示铺设板的方法数量。

复杂度分析

时间复杂度

矩阵幂运算方法的时间复杂度可以分解为两个主要部分：矩阵乘法和矩阵幂运算。

矩阵乘法

在此方法中，我们主要处理 3x3 矩阵。

相乘两个 3x3 矩阵涉及将第一个矩阵的每一行元素与第二个矩阵的列相乘，这需要 3×3×3=27 次 标量乘法和加法。

由于矩阵的大小是常数 (3x3)，每次矩阵乘法运算都以常量时间执行，表示为 O(1)。

矩阵幂运算

矩阵幂运算利用了平方求幂方法。此方法有效地将矩阵提升到幂。

平方求幂通过重复平方基矩阵并最多进行 log n 次乘法来减少所需的乘法次数，其中 n 是板的长度。

每次矩阵的平方或乘法（作为 O(1) 操作）会导致幂运算过程的时间复杂度为 O(logn)。

总体时间复杂度

此算法的总体时间复杂度为 O(logn)。之所以实现这种效率，是因为 矩阵幂运算函数将所需的操作数量减少到了对数时间，使其比通常具有 线性时间复杂度的直接迭代或递归方法快得多。

空间复杂度

矩阵幂运算方法所占用的空间复杂度非常高效。

矩阵存储

该算法使用几个 3x3 矩阵。每个矩阵需要 9 个单位的空间（因为 3×3=9）。

由于矩阵是 大小恒定的，存储它们所需的空间也是恒定的，表示为 O(1)。

函数调用堆栈

矩阵幂运算函数是迭代实现的，而不是递归实现的。因此，不需要为调用堆栈分配额外的空间，而递归方法需要调用堆栈。

迭代函数调用使用的空间是 常量 O(1)。

结果存储

铺设 2×n 板的方法数量的最终结果是一个标量值。存储此结果需要 O(1) 的空间。

总体空间复杂度

该算法的空间复杂度为 O(1)，表示它使用的空间量是恒定的，与输入大小 n 无关。这包括存储矩阵和计算过程中任何中间结果的空间。

下一主题C/C++ 中的 c32rtomb() 函数

C++ 多米诺骨牌和三米诺骨牌铺设

多米诺骨牌和三格骨牌

方法一：动态规划方法

程序

说明

复杂度分析

方法二：矩阵幂运算

程序

说明

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 多米诺骨牌和三米诺骨牌铺设

多米诺骨牌和三格骨牌

方法一：动态规划方法

程序

说明

复杂度分析

方法二：矩阵幂运算

程序

说明

复杂度分析

相关帖子

C++ std::filesystem::perm_options

C++ 中使用 Pell 数查找

C++ 中的 std::has_single_bit

C++ 中打印内部递减模式

C++ 中的莱兰数

C++ 旋转卡尺

C++ 中的 Geek-onacci 数

C++ 中的终止进程

C++ 中检查主教是否可以吃掉兵

C++ 中的帕多万序列

订阅 Tpoint Tech