painting-a-grid-with-three-different-colors

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two integers <code>m</code> and <code>n</code>. Consider an <code>m x n</code> grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted.

Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/22/colorthegrid.png" style="width: 200px; height: 50px;" />
<pre>
Input: m = 1, n = 1
Output: 3
Explanation: The three possible colorings are shown in the image above.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/22/copy-of-colorthegrid.png" style="width: 321px; height: 121px;" />
<pre>
Input: m = 1, n = 2
Output: 6
Explanation: The six possible colorings are shown in the image above.
</pre>

Example 3:

<pre>
Input: m = 5, n = 5
Output: 580986
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= m &lt;= 5</code></li>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
</ul>

colorTheGrid

Painting a Grid With Three Different Colors

Number of Ways to Paint N × 3 Grid

number-of-ways-to-paint-n-3-grid

给 N x 3 网格图涂色的方案数

Dynamic Programming

给你两个整数 <code>m</code> 和 <code>n</code> 。构造一个 <code>m x n</code> 的网格，其中每个单元格最开始是白色。请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。

涂色方案需要满足：不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。因为答案可能非常大， 返回 对 <code>109 + 7</code> 取余 的结果。

 

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/22/colorthegrid.png" style="width: 200px; height: 50px;" />
<pre>
输入：m = 1, n = 1
输出：3
解释：如上图所示，存在三种可能的涂色方案。
</pre>

示例 2：
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/22/copy-of-colorthegrid.png" style="width: 321px; height: 121px;" />
<pre>
输入：m = 1, n = 2
输出：6
解释：如上图所示，存在六种可能的涂色方案。
</pre>

示例 3：

<pre>
输入：m = 5, n = 5
输出：580986
</pre>

 

提示：

<ul>
	<li><code>1 <= m <= 5</code></li>
	<li><code>1 <= n <= 1000</code></li>
</ul>