$$ \newcommand\Tr{\mathrm{Tr}} \newcommand{\braket}[2]{\langle #1 \mid #2 \rangle} \newcommand\I{\mathbb{I}} \newcommand{\avg}[1]{\left< #1 \right>} \newcommand{\RD}{D} \newcommand{\ri}{\mathrm{i}} \DeclareMathOperator{\sign}{sign} \DeclareMathOperator{\Sign}{Sign} \newcommand{\ii}{\mathrm i} \newcommand{\vv}{\mathrm v} \newcommand{\ff}{\mathrm f} \newcommand{\mm}{\mathrm m} \newcommand{\ee}{\mathrm e} \newcommand{\xx}{\mathrm x} \newcommand{\RR}{\mathrm R} \newcommand{\dd}{\mathrm d} \newcommand{\FF}{\mathrm F} \newcommand{\BB}{\mathrm B} \newcommand{\vph}{v_{\mathrm{ph}}} $$

Paint Fence

Problem

We have to paint fence consists of n posts with k different colors with below rules:

  • Every post must be painted with one and only one color
  • Three or more consecutive posts cannot be painted with the same color

Our task is to find the number of ways to paint the fence.

For example,

Input: n = 3, k = 2
Output: 6
Input: n = 1, k = 1
Output: 1
Input: n = 7, k = 2
Output: 42

Constraints:

  • 1 <= n <= 50
  • 1 <= k <= 105

Solution

Brute Force

public int NumWays(int n, int k)
{
    return NumWays(n);

    int NumWays(int n)
    {
        if (n == 1)
            return k;

        if (n == 2)
            return k * k;

        return (k - 1) * (NumWays(n - 1) + NumWays(n - 2));
    }
}

Complexity Analysis

  • Time Complexity: At each step we generate two subtree and the height of the tree is n. The total number of generated nodes is 2n. Since, we traverse all the nodes, then the complexity will be O(2n).
  • Space Complexity: The complexity will be the same with O(recursion depth), thus it will be O(n).

Top-down Dynamic Programming

public int NumWays(int n, int k)
{
    Dictionary<int, int> memo = new Dictionary<int, int>();
    return NumWays(n);

    int NumWays(int n)
    {
        if (n == 1)
            return k;

        if (n == 2)
            return k * k;

        if (memo.ContainsKey(n))
        {
            return memo[n];
        }

        memo.Add(n, (k - 1) * (NumWays(n - 1) + NumWays(n - 2)));
        return memo[n];
    }
}

Complexity Analysis

  • Time Complexity: Since we cache each NumWays(n), then we will perform at most n recursive calls, thus the complexity is O(n).
  • Space Complexity: The complexity will be the same with O(recursion depth), thus it will be O(n).

Bottom-up Dynamic Programming

public int NumWays(int n, int k)
{
    if (n == 1)
        return k;

    if (n == 2)
        return k * k;

    int[] numWays = new int[n + 1];
    numWays[1] = k;
    numWays[2] = k * k;

    for (int i = 3; i <= n; i++)
    {
        numWays[i] = (k - 1) * (numWays[i - 1] + numWays[i - 2]);
    }

    return numWays[n];
}

Complexity Analysis

  • Time Complexity: Since we iterate linearly up to n, then the complexity is O(n).
  • Space Complexity: O(n) since we allocate n+1 spaces for caching (tabulation).

Bottom-up Dynamic Programming, Constant Space

public int NumWays(int n, int k)
{
    if (n == 1) return k;

    int twoPostsBack = k;
    int onePostBack = k * k;

    for (int i = 3; i <= n; i++)
    {
        int curr = (k - 1) * (onePostBack + twoPostsBack);
        twoPostsBack = onePostBack;
        onePostBack = curr;
    }

    return onePostBack;
}

Complexity Analysis

  • Time Complexity: Since we iterate linearly up to n, then the complexity is O(n).
  • Space Complexity: O(1) since we can replace the array with two variables to track previous results.