Paint fence

Dynamic Programming

48.3% acceptance

Mar 31, 2026

1639

397

You are painting a fence of n posts with k different colors. You must paint the posts following these rules: Every post must be painted exactly one color. There cannot be three or more consecutive posts with the same color. Given the two integers n and k, return the number of ways you can paint the fence.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn num_ways(n: i32, k: i32) -> i32 {
    if n == 0 { return 0; }
    if n == 1 { return k; }
    // same = ways where last two are same color
    // diff = ways where last two are different color
    let mut same = k;       // for n=2
    let mut diff = k * (k - 1); // for n=2
    for _ in 3..=n {
      let new_same = diff;
      let new_diff = (same + diff) * (k - 1);
      same = new_same;
      diff = new_diff;
    }
    same + diff
  }
}