数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++程序：计算用多米诺骨牌和三连块填充区域的配置数量
假设我们有两种形状，多米诺骨牌和三连块。多米诺骨牌是 2 x 1 的形状，三连块是“L”形。它们可以像下面这样旋转：
如果我们有一个数字 n，我们需要找到用这两种类型的碎片填充 2 x n 棋盘的配置数量。众所周知，在铺砖中，每个方格都必须被一个瓷砖覆盖。
因此，如果输入是 3，则输出将是 5。因此，排列可以是 [XYZ XXZ XYY XXY XYY] 和 [XYZ YYZ XZZ XYY XXY]，这里不同的字母用于不同的瓷砖。
为了解决这个问题，我们将遵循以下步骤：
创建一个名为 dp 的大小为 N + 5 的数组，设置 dp[1] := 1，dp[2] := 2 和 dp[3] := 5
对于 i 从 4 到 N 的范围
dp[i] := 2*dp[i − 1] + dp[i − 3]
返回 dp[N]
让我们看看下面的实现，以便更好地理解：
示例
#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 solve(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.solve(3));
}输入
3
输出
5
更新于: 2020-12-25
74 次浏览
广告