Re: [閒聊] 每日leetcode
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
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.48.170 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1747639534.A.A51.html
推
05/19 15:32,
6月前
, 1F
05/19 15:32, 1F
推
05/19 15:37,
6月前
, 2F
05/19 15:37, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1430 之 1548 篇)：