Re: [閒聊] 每日leetcode
※ 引述《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
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1747785758.A.418.html
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 1432 之 1548 篇)：