Medium

Paint Fence

LAB

Return the number of ways to paint n fence posts with k colors so no more than two adjacent posts have the same color.

EXAMPLES

Example 1

Input
{
  "n": 3,
  "k": 2
}

Output
6

FUNCTION SHAPE

n: intk: int→int

SOLUTION NOTE

Track if current matches previous. If two consecutive match, next must differ.

Reveal reference solution +

pythonREFERENCE

def numWays(self, n: int, k: int) -> int:
    if n == 1: return k

    @cache
    def dp(i, same_as_prev):
        if i == n:
            return 1
        if same_as_prev:
            # Must pick different color
            return (k - 1) * dp(i + 1, False)
        else:
            # Can pick same (1 way) or different (k-1 ways)
            return dp(i + 1, True) + (k - 1) * dp(i + 1, False)

    return k * dp(1, False)

TimeO(n)

SpaceO(n)

Open on LeetCode ↗