1931. Painting a Grid With Three Different Colors
https://leetcode.com/problems/painting-a-grid-with-three-different-colors/
题意：
一个 m×n 的表格
每个格子可以画三种颜色
问邻色不重复有几种画法
思路：
这题目是状态压缩 + dp
状态压缩 是因为不可能一个一个状态去搞 太多了 一定 TLE
看题目给 m 最大是 5 其实就能猜一下
接着你如果要搞状态压缩
这边的压缩主要是因为可用颜色有三种
因此可以做一个三进位数来表示每一格的状态
m = 5 就是 3×3×3×3×3 代表五个格子都有三种色的可能性 (0, 1, 2 代表三种色)
用 m % 3 之后 m / 3 可以解压缩 得到每一格原本的状态
再来因为相邻同色就不合法
可以先状态还原 把相邻重复的去掉
在 m = 5 的情况可以从 3 ^ 5 的 243 变成 48 种
大幅提升效率
搞完状态压缩表后
可以开始 dp
就是每次你的新 dp 状态都是拿 n-1 的状态去接刚刚的合法状态 Vec
虽然合法状态本身合法 但接在一起可能上下 m 相邻同色不合法
所以还要判断一下新状态是否合法
这边用一个状态转移阵列 HashMap<usize, Vec<usize>>
针对 n-1 的每个 m 状态寻找符合这个 m 的下一列合法状态
另外要使用 new_dp 来储存
不然你会在同一个 dp 涂改 会出现问题
Code:
我本来的写得很烂
下面让 AI 改过跟加注解比较清楚逻辑
use std::collections::HashMap;
impl Solution {
pub fn color_the_grid(m: i32, n: i32) -> i32 {
const MOD: u64 = 1_000_000_007;
let m = m as usize;
let n = n as usize;
let max_state = 3usize.pow(m as u32);
// Step 1: 取得所有合法的单列状态
let valid_states: Vec<usize> = (0..max_state)
.filter(|&s| Self::is_valid_row(s, m))
.collect();
// Step 2: 建立转移表
let transitions = Self::build_transition_table(&valid_states, m);
// Step 3: 初始化 dp（列 0）
let mut dp = vec![0u64; max_state];
for &state in &valid_states {
dp[state] = 1;
}
// Step 4: 从第 1 列到第 n-1 列递推
for _ in 1..n {
let mut new_dp = vec![0u64; max_state];
for &s1 in &valid_states {
for &s2 in &transitions[&s1] {
new_dp[s2] = (new_dp[s2] + dp[s1]) % MOD;
}
}
dp = new_dp;
}
// Step 5: 回传结果
(dp.iter().fold(0, |acc, &x| (acc + x) % MOD)) as i32
}
// 检查一列是否合法（不能有相邻同色）
fn is_valid_row(mut state: usize, m: usize) -> bool {
let mut prev = 3; // 不可能的颜色
for _ in 0..m {
let color = state % 3;
if color == prev {
return false;
}
prev = color;
state /= 3;
}
true
}
// 检查两列是否可以相邻（每格对应不同色）
fn is_compatible(mut a: usize, mut b: usize, m: usize) -> bool {
for _ in 0..m {
if a % 3 == b % 3 {
return false;
}
a /= 3;
b /= 3;
}
true
}
// 建立转移表：哪些列状态可以相邻
fn build_transition_table(states: &Vec<usize>, m: usize) -> HashMap<usize,
Vec<usize>> {
let mut table: HashMap<usize, Vec<usize>> = HashMap::new();
for &a in states {
for &b in states {
if Self::is_compatible(a, b, m) {
table.entry(a).or_default().push(b);
}
}
}
table
}
}

大师

大师