数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++程序中N×3网格的涂色方法数
假设我们有一个大小为n x 3的网格，我们想用三种颜色中的每一种来涂色网格的每个单元格。这里使用的颜色是红色、黄色和绿色。
现在有一个约束条件，即不允许两个相邻的单元格具有相同的颜色。网格有n行。最后，我们必须找到可以涂色此网格的方法数。答案可能非常大，因此返回它模10^9 + 7的结果。
因此，如果输入是1，则输出将为12。
为了解决这个问题，我们将遵循以下步骤：
m = 10^9 + 7
定义一个函数add()，它将接收a, b,
返回((a mod m) + (b mod m)) mod m
从主方法执行以下操作：
a123 := 6, a121 = 6
初始化i := 2，当i −= n时，更新（将i增加1），执行：
b121 := add(3 * a121, 2 * a123)
b123 := add(2 * a121, 2 * a123)
a121 := b121
a123 := b123
返回add(a123, a121)
示例
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli mod = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ((a % mod) + (b % mod)) % mod;
}
int numOfWays(int n){
lli a123 = 6, a121 = 6;
lli b123, b121;
for (int i = 2; i <= n; i++) {
b121 = add(3 * a121, 2 * a123);
b123 = add(2 * a121, 2 * a123);
a121 = b121;
a123 = b123;
}
return add(a123, a121);
}
};
main(){
Solution ob;
cout << (ob.numOfWays(3));
}输入
3
输出
246
更新于：2020年7月21日
114 次浏览
广告