数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律学用 C++ 进行多米诺骨牌和多米诺骨牌三块拼图贴图
假设我们有两种类型的形状，多米诺骨牌和多米诺骨牌三块拼图。它们可以像下面这样旋转：
在贴图中，每个方块都必须被图块覆盖。如果棋盘上有两个沿 4 个方向相邻的单元格，并且恰好有一个贴图使这两个方块都被图块占据，则这两个贴图不同。
给定 N，那么我们必须找到用 2xN 棋盘拼图的方法有多少种？因此，如果输入为 3，则输出将为 5。因此，排列可以是 [XYZ XXZ XYY XXY XYY] 和 [XYZ YYZ XZZ XYY XXY]，这里使用不同的字母表示不同的图块。
要解决此问题，我们将遵循以下步骤：
创建一个名为 dp 的大小为 N + 5 的数组，设置 dp[1] := 1，dp[2] := 2 和 dp[3] := 5
对于范围 4 到 N 中的 i
dp[i] := 2*dp[i – 1] + dp[i – 3]
返回 dp[N]
示例 (C++)
让我们看看以下示例以获得更好的理解：
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int add(int a, int b){
return ((a % MOD) + (b % MOD)) % MOD;
}
class Solution {
public:
int numTilings(int N) {
vector <int> dp(N + 5);
dp[1] = 1;
dp[2] = 2;
dp[3] = 5;
for(int i = 4; i <= N; i++){
dp[i] = add(2 * dp[i - 1], dp[i - 3]);
}
return dp[N];
}
};
main(){
Solution ob;
cout << (ob.numTilings(3));
}输入
3
输出
5
更新于：02-五月-2020
367 次浏览
广告