描述用红色的 11 和黑色的 22 两种规格的瓷砖不重叠地铺满 n3 的路面求出有多少种不同的铺设方案结果模12345输入描述仅仅包含一个整数 n。输出描述仅包含一个整数表示铺设方案的数量。用例输入 1 2用例输出 1 3提示数据范围：0 n 1000 。cpp

解法思路：

题目要求用红色的11和黑色的22两种规格的瓷砖不重叠地铺满n*3的路面，求出有多少种不同的铺设方案。

我们可以使用动态规划来解决这个问题。定义一个dp数组，dp[i]表示铺满i*3的路面的方案数。

对于dp数组的每个元素，都有两种选择：

1. 如果当前位置铺上一块红色的1*1瓷砖，那么剩下的路面就是(i-1)*3，可以有dp[i-1]种方案。
2. 如果当前位置铺上一块黑色的2*2瓷砖，那么剩下的路面就是(i-2)*3，可以有dp[i-2]种方案。

所以，dp[i] = dp[i-1] + dp[i-2]。

最终的答案就是dp[n]。

具体实现代码如下：

#include <iostream>
#include <vector>
using namespace std;

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

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

    for (int i=2; i<=n; i++) {
        dp[i] = (dp[i-1] + dp[i-2]) % 12345;
    }

    cout << dp[n] << endl;

    return 0;
}

复杂度分析：

时间复杂度：O(n)。需要计算dp数组的n个元素。 空间复杂度：O(n)。需要使用一个大小为n+1的dp数组