递推问题之简易俄罗斯方块c++

Question

简易俄罗斯方块（tetris.cpp)
【问题描述】
小明有一个长为 N 宽为 2 的矩形，给你两种俄罗斯方块：一个长 2 宽 1，另一个是 L
型覆盖 3 个方形的方块。如下图：

方块可以旋转，并可以无限制提供。小明的任务是计算用这两种来覆盖 N* 2 的矩形的
覆盖方法。例如一个 23 的矩形可以有 5 种覆盖方法，如下：（用 0，1，2 表示不同的方块）
2
012 002 011 001 011
012 112 022 011 001
注意可以使用两种砖头混合起来覆盖，如 24 的墙可以这样覆盖：
0112
0012
给定 N，要求计算 2* N 的矩形的覆盖方法。由于结果很大，所以只要求输出最后 4 位。
例如 2* 13 的覆盖方法为 13465，只需输出 3465 即可。如果答案少于 4 位，就直接输出就
可以，不用加前导 0，如 N=3 时输出 5。
【输入格式】
一个整数 N，表示矩形的长，宽度固定为 2。
【输出格式】
输出覆盖方法的最后 4 位，如果不足 4 位就输出整个答案。
【输入输出样例 1】
tetris.in
7
tetris.out
117
【输入输出样例 2】
tetris.in
13
tetris.out
3465
【输入输出样例 3】
tetris.in
198
tetris.out
9365
【输入输出样例 4】
tetris.in
5
tetris.out
24
【数据说明】
对于 40% 的数据，1<=n<=10；
对于 100% 的数据，1<=n<=10^6；

Answer 1

该回答引用自GPT-3.5,由博主GIS_Liu编写：

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 10000;

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

    vector<int> dp(N + 1, 0);
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= N; ++i) {
        dp[i] = (dp[i - 1] + dp[i - 2] * 2) % MOD;
    }

    cout << dp[N] << endl;

    return 0;
}

解题思路：

这是一个经典的动态规划问题。我们可以定义状态 dp[i] 表示覆盖 2 * i 的矩形的方法数。显然，dp[0] = 1，dp[1] = 1。

对于 dp[i]，我们可以考虑最后一块砖的形状，有两种情况：

1. 如果最后一块砖是竖直的，则前面的矩形长度为 i - 1，此时只能放一个 2 * 1 的砖，所以方法数为 dp[i - 1]。
2. 如果最后一块砖是水平的，则前面的矩形长度为 i - 2，此时可以放两个 2 * 1 的砖或一个 L 型砖，所以方法数为 dp[i - 2] * 2。

综上，状态转移方程为 dp[i] = dp[i - 1] + dp[i - 2] * 2。

由于需要输出最后 4 位，所以在计算过程中每次取模 10000。

如果该回答解决了您的问题，请采纳！如果没有，请参考以下方案进行修订