1. 題目

你有一個 n x 3 的網格圖 grid ，你需要用 紅，黃，綠 三種顏色之一給每一個格子上色，且確保相鄰格子顏色不同（也就是有相同水平邊或者垂直邊的格子顏色不同）。

給你網格圖的行數 n 。

請你返回給 grid 涂色的方案數。由于答案可能會非常大，請你返回答案對 10^9 + 7 取余的結果。

示例 1： 輸入：n = 1 輸出：12 解釋：總共有 12 種可行的方法：示例 2： 輸入：n = 2 輸出：54示例 3： 輸入：n = 3 輸出：246示例 4： 輸入：n = 7 輸出：106494示例 5： 輸入：n = 5000 輸出：30228214提示： n == grid.length grid[i].length == 3 1 <= n <= 5000

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/number-of-ways-to-paint-n-x-3-grid
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 顏色分為2種類型 ABA型，ABC型
  
• 1個ABA 可以產生 3個ABA + 2個ABC
• 1個ABC 可以產生 2個ABA + 2個ABC

class Solution { public:int numOfWays(int n) {long aba = 6, abc = 6, aba_t, abc_t, mod = 1e9+7;for(int i = 1; i < n; ++i){aba_t = (3*aba+2*abc)%mod;abc_t = (2*(aba+abc))%mod;aba = aba_t;abc = abc_t;}return (aba+abc)%mod;} };

4 ms 5.8 MB

總結

以上是生活随笔為你收集整理的LeetCode 1411. 给 N x 3 网格图涂色的方案数（数学）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。