※ 引述《yam276 (史莱哲林的优等生)》之铭言：
: 1931. Painting a Grid With Three Different Colors
: https://leetcode.com/problems/painting-a-grid-with-three-different-colors/
: 这题目是状态压缩 + dp
顺便写了一下类似题练习
1411. Number of Ways to Paint N × 3 Grid
https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/
题意：
跟1931类似，但是这次比较简单
只有 m = 3 的情况，求第 n 行的合法情况
既然只有三格，那就用 const 阵列来搞
因为只有 3x2x2 = 12 种情况
然后建立转移矩阵
计算之后 n-1 的列有几种合法情况
我发现 Rust 可以用 const fn 来让他编译阶段就算完
最后就是一样两个状态阵列 prev curr
prev 给 curr 计算之后把 curr 复制回 prev
Code:
impl Solution {
pub fn num_of_ways(n: i32) -> i32 {
const MOD: u64 = 1_000_000_007;
const PATTERNS: [(u8, u8, u8); 12] = [
(0, 1, 0),
(0, 1, 2),
(0, 2, 0),
(0, 2, 1),
(1, 0, 1),
(1, 0, 2),
(1, 2, 0),
(1, 2, 1),
(2, 0, 1),
(2, 0, 2),
(2, 1, 0),
(2, 1, 2),
];
const fn is_comptaible(a: (u8, u8, u8), b: (u8, u8, u8)) -> bool {
if a.0 == b.0 || a.1 == b.1 || a.2 == b.2 {
return false;
}
true
}
const fn build_transition() -> [[bool; 12]; 12] {
let mut arr = [[false; 12]; 12];
let mut i = 0;
while i < 12 {
let mut j = 0;
while j < 12 {
arr[i][j] = is_comptaible(PATTERNS[i], PATTERNS[j]);
j += 1;
}
i += 1;
}
arr
}
const TRANSITION: [[bool; 12]; 12] = build_transition();
let mut prev = [1u64; 12];
let mut curr = [0u64; 12];
for _ in 1..n {
for i in 0..12 {
curr[i] = 0;
for j in 0..12 {
if TRANSITION[i][j] {
curr[i] = (curr[i] + prev[j]) % MOD;
}
}
}
prev.copy_from_slice(&curr);
}
prev.iter().fold(0u64, |acc, &x| (acc + x) % MOD) as i32
}
}