276 Paint Fence

Problem

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.

Example 1:

example 1 image

Input: n = 3, k = 2
Output: 6
Explanation: All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

Example 2:

Input: n = 1, k = 1
Output: 1

Example 3:

Input: n = 7, k = 2
Output: 42

Constraints:

• 1 <= n <= 50
• 1 <= k <= 10⁵
• The testcases are generated such that the answer is in the range [0, 2³¹ - 1] for the given n and k.

Bottom-up Dynamic Programming

Intuition

Right after finish reading the question, I feel I should calculate subproblems of the final problem and the subproblems are overlapped. In addition, the questions asks for number of ways.

These are all signals that indicate this is a dynamic programming question. In general, there are four steps to solve a dynamic programming question:

1. Divide a complex problem into a number of simpler overlapping subproblems
   • some would say this step is to define the optimal solution
2. Define a recurrence relation to solve larger subproblems from smaller subproblems
3. Store solutions to each of these subproblems, solving each subproblem only once
4. Use stored solutions to solve the original problem

Algorithm

1. Let 2D array opt[i][j] denote the optimal number of ways to paint post i with color j

• Initialize the array: for opt[i][j] where i == 0, opt[i][j] = 1 and where i == 1, opt[i][j] = k

2. The recurrence relation for i >= 2 is opt[i][j] = sigma(opt[i-1][!j]) + sigma(opt[i-2][!j])
3. Iterate i from 2 to n-1, build and store the solutions for each subproblem
4. The solution to the original problem is sigma(opt[n-1][j]) where j = [0, k)

Implementation

class Solution {
    public int numWays(int n, int k) {
        if (n == 1) { return k; }
        if (k == 1) { return n > 2 ? 0 : 1; }
        // define the optimal solution
        int[][] opt = new int[n][k];
        
        // init
        for (int i = 0, j = 0; j < k; j++) {
            opt[i][j] = 1;
        }        
        for (int i = 1, j = 0; j < k; j++) {
            opt[i][j] = k;
        }
        
        // solve subproblems
        for (int i = 2; i < n; i++) {
            int pp = 0, p = 0;
            for (int x = i-1, y = 0; y < k; y++) { p += opt[x][y]; }
            for (int x = i-2, y = 0; y < k; y++) { pp += opt[x][y]; }
            for (int j = 0; j < k; j++) {
                opt[i][j] = p - opt[i-1][j] + pp - opt[i-2][j];
            }
        }
        
        // solve the original problem 
        int numWays = 0;
        for (int i = n-1, j = 0; j < k; j++) { numWays += opt[i][j]; }
        return numWays;
    }
}

Complexity Analysis

Time Complexity

O(n*k)

We iterate n times and each time we calculate the sum of previous row, which is of size k

Space Complexity

O(n*k)

We created a 2D array to store the optimal solution for each subproblem.

Dynamic Programming (Time and Space Improvement)

Intuition

Though it can be accepted by the judge, the first solution is a little time & space consuming. Let’s examine the problem more carefully:

When painting the 1^st post, we have k ways.

When painting the 2^nd post, we have k*k ways, since we can have two consecutive posts colored with the same color.

When painting the 3^rd post, we have to pay attention as the question doesn’t allow three consecutive posts colored with the same color. How do we achieve that?

The answer is simple: break the harmony! Let the last three posts not being able to form the same color. Here is how:

Pick a color that is other than the color of the 2^nd post.

This complies the constraint by the fact that at least the 3^rd post and the 2^nd post are not painted with the same color.

Here don’t waste your time thinking about what exact color the 2^nd post was painted with, otherwise you’ll be swallowed by the black hole (just kidding). Just imagine that the 2^nd post picked one color, then you have k-1 options now. Hence you can paint in k*k * (k-1) ways.

You may ask how about the colors of the 2^nd and the 1^st post in this case, will they be painted with the same color? May be the same maybe not, but we don’t care! It doesn’t break any rule set by the question.

Pick a color that is other than the color of the 1^st post.

This complies the constraint by the fact that at least the 3^rd post and the 1^st post are not painted with the same color.

Same here, just imagine that the 1^st post picked one color, then you have k-1 colors to choose, hence there are 1 * (k-1) ways to paint.

Hence, the optimal number of ways to paint the 3^rd post is k*k * (k-1) + 1 * (k-1), i.e. (k*k + 1) * (k-1).

…

When painting the i^th post, the number of ways is (ways(i-1) + ways(i-2)) * (k-1).

Great! It looks like we don’t need to know the exact color of a post at all in our solution.

Algorithm

1. Let 1D array opt[i] denote the optimal number of ways to paint posts [0,i]
   • Initialzie the array: opt[0] = k and opt[1] = k*k
2. The recurrence relation for i >= 2 is opt[i] = (opt[i-1] + opt[i-2]) * (k-1)
3. Iterate i from 2 to n-1, build and store the solutions for each subproblem
4. The solution to the original problem is opt[n-1]

Implementation

class Solution {
    public int numWays(int n, int k) {
        // corner case
        if (n == 1) return k;
        if (k == 1) return n == 2 ? 1 : 0;
        
        // define the optimal solution
        int[] opt = new int[n];
        
        // init
        opt[0] = k;
        opt[1] = k*k;
        
        // recurrence relation
        for (int i = 2; i < n; i++) {
            opt[i] = (opt[i-1] + opt[i-2]) * (k-1);
        }
        
        return opt[n-1];
    }
}

Complexity Analysis

Time Complexity

O(n)

We traverse the array in one pass.

Space Complexity

O(n)

We create an auxiliary 1D array to store the optimal solution for each subproblem.

Dynamic Programming (Further Space Improvement)

Intuition

In the previous solution, for each subproblem opt[i] we only need to keep opt[i-1] and opt[i-2] in order to calculate its value. We don’t need an array to store each state for this question.

Algorithm

1. Let p be the optimal solution for previous post, and pp be the one before previous post

• Initialzie the variables: pp = k and p = k*k

2. The recurrence relation is the optimal number of ways for the current post is (pp + p) * (k-1)
3. Iterate i from 2 to n-1, caculate optimal solution for current subproblem and shift the values of pp and p
4. The solution to the original problem is p

Implementation

class Solution {
    public int numWays(int n, int k) {
        // corner case
        if (n == 1) return k;
        if (k == 1) return n == 2 ? 1 : 0;
        
        int pp = k, p = k*k;
        
        for (int i = 2; i < n; i++) {
            int cur = (pp + p)*(k - 1);
            pp = p;
            p = cur;
        }
        
        return p;
    }
}

Complexity Analysis

Time Complexity

O(n)

We only have one for loop and in the worse case it has n-2 iterations.

Space Complexity

O(1)

We only create two variables to store the previous state.