資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告