Jan 3

LC-1411: Number of Ways to Paint N × 3 Grid (Rust)

Dynamic dp problem. I had the base case in mind, but the loop required some mathematics. 
Watching this page over and over again did the magic: https://www.youtube.com/watch?v=W-WvItFiWX8

impl Solution {
    pub fn num_of_ways(n: i32) -> i32 {
        let modu = 1_000_000_007i64;
        
        if n == 1 {
            return 12;
        }

        // base case
        let mut abc = 6i64;
        let mut aba = 6i64;

        for _ in 1..n {
            let next_aba = (3 * aba + 2 * abc) % modu;
            let next_abc = (2 * aba + 2 * abc) % modu;

            aba = next_aba;
            abc = next_abc;
        }

        ((aba + abc) % modu) as i32
    }
}


I was initially hitting an error via this line:  let modu = 1_000_000_007; due to integer overflow with big numbers.