Leetcode 1411:给Nx3网格图涂色的方案数(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1411:给Nx3网格图涂色的方案数(超详细的解法!!!)

in leetcode with 0 comment

你有一个 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

提示:

解题思路

首先比较容易想到的思路就是记忆化加递归,每次枚举每个位置的颜色使其和上边和左边的颜色不同即可。当枚举到最后一行最后一列的时候,返回当前位置可选的颜色数目即可。

from functools import lru_cache
class Solution:
    def numOfWays(self, n: int) -> int:
        mod = 10 ** 9 + 7
        s1 = set([1, 2, 3])
        
        @lru_cache(None)
        def dfs(x, y, pre, cur):
            s2 = [pre[y]]
            if y: s2.append(cur[y - 1])
            t = list(s1 - set(s2)) # 当前位置可以使用的颜色
            
            if y == 2:
                if x == n - 1: return len(t)
                res = 0
                for i in t:
                    t_cur = list(cur)
                    t_cur[y] = i
                    res = (res + dfs(x + 1, 0, tuple(t_cur), (0, 0, 0))) % mod
                return res

            res = 0
            for i in t:
                t_cur = list(cur)
                t_cur[y] = i
                res = (res + dfs(x, y + 1, pre, tuple(t_cur))) % mod
            return res

        return dfs(0, 0, (0, 0, 0), (0, 0, 0))

这个问题还有一个非常简洁的思路,对于每一行的颜色,考虑其分布规律可以分成两种形式:1)两边的颜色相同aba。2)三个位置颜色都不相同abc

那么,第一行按照第一种形式可以是:121131212232313323。按照第二种形式的话可以有:123132213231312321

接着思考第二层的摆放,如果第一层是121的话,那么第二层可以是212213232312313,对于其他第一种形式的类似,都会有3aba2abc情况。如果第一层是第二种形式的话,都会有2aba2abc的情况。可以定义函数$f_{aba}(n)$表示第naba这种摆放方式的数目,可以定义$f_{abc}(n)$表示第nabc这种摆放方式的数目,那么:

最后的结果显然就是$f_{abc}(n)+f_{aba}(n)$。

class Solution:
    def numOfWays(self, n: int) -> int:
        aba, abc, mod = 6, 6, 10**9 + 7
        for i in range(n - 1):
            aba, abc = aba * 3 + abc * 2, aba * 2 + abc * 2
        return (aba + abc) % mod

reference:

https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/discuss/574923/JavaC%2B%2BPython-DP-O(1)-Space

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses