Painting a grid with three different colors

Dynamic Programming

77.3% acceptance

Feb 25, 2026

934

You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted. Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo 109 + 7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn color_the_grid(m: i32, n: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let m = m as usize;

    // Generate all valid column colorings (no two adjacent same color)
    let mut valid_cols: Vec<Vec<u8>> = Vec::new();
    Self::gen_cols(m, &mut vec![], &mut valid_cols);

    let k = valid_cols.len();
    // Precompute which column pairs are compatible (no same color in same row)
    let mut compat = vec![vec![]; k];
    for i in 0..k {
      for j in 0..k {
        if (0..m).all(|r| valid_cols[i][r] != valid_cols[j][r]) {
          compat[i].push(j);
        }
      }
    }

    let mut dp = vec![1i64; k];
    for _ in 1..n {
      let mut new_dp = vec![0i64; k];
      for j in 0..k {
        for &i in &compat[j] {
          new_dp[j] = (new_dp[j] + dp[i]) % MOD;
        }
      }
      dp = new_dp;
    }
    (dp.iter().sum::<i64>() % MOD) as i32
  }

  fn gen_cols(m: usize, cur: &mut Vec<u8>, result: &mut Vec<Vec<u8>>) {
    if cur.len() == m {
      result.push(cur.clone());
      return;
    }
    for c in 0..3u8 {
      if cur.is_empty() || *cur.last().unwrap() != c {
        cur.push(c);
        Self::gen_cols(m, cur, result);
        cur.pop();
      }
    }
  }
}