Compute the Number of Ways to Paint the House via Dynamic Programming Algorithm

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

Example:
Input: n = 3, k = 2
Output: 6
Explanation: Take c1 as color 1, c2 as color 2. All possible ways are:

            post1  post2  post3      
 -----      -----  -----  -----       
   1         c1     c1     c2 
   2         c1     c2     c1 
   3         c1     c2     c2 
   4         c2     c1     c1  
   5         c2     c1     c2
   6         c2     c2     c1

Using Dynamic Programming to Paint the House

In last post: How to Paint The Houses using Minimal Costs via Dynamic Programming Algorithm?, we discuss the algorithm to paint the house with the minimal cost.

In this post, we will discuss using the same Dynamic Programming algorithm to compute the number of different ways to paint the house subject to one criteria: no same colours for 3 consecutive houses in a row.

If we use F(n) to denote the answer, we can easily have the following:

1
2
3
4

F[0] = 0;
F[1] = k;
F[2] = k * k;
F[n] = (k - 1) * (F[n - 1] + F[n - 2]);

F[0] = 0;
F[1] = k;
F[2] = k * k;
F[n] = (k - 1) * (F[n - 1] + F[n - 2]);

It is straightforward to define/compute the first few F values. When we paint the house n, we might have two choices: paint a different colour than house n-1, which will be answer F[n-1]*(k-1) choices, or with the same colour as house n-1, which will be answer F[n-2]*(k-1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int numWays(int n, int k) {
        vector<int> f(n + 1);
        f[0] = 0;
        if (n == 0) return f[0];
        f[1] = k;
        if (n == 1) return f[1];
        f[2] = k * k;
        if (n == 2) return f[2];
        for (int i = 3; i <= n; ++ i) {
            f[i] = f[i - 1] * (k - 1) + // different color 
                f[i - 2] * (k - 1); // same color
        }
        return f[n];
    }
};

class Solution {
public:
    int numWays(int n, int k) {
        vector<int> f(n + 1);
        f[0] = 0;
        if (n == 0) return f[0];
        f[1] = k;
        if (n == 1) return f[1];
        f[2] = k * k;
        if (n == 2) return f[2];
        for (int i = 3; i <= n; ++ i) {
            f[i] = f[i - 1] * (k - 1) + // different color 
                f[i - 2] * (k - 1); // same color
        }
        return f[n];
    }
};

This Dynamic Programming is a bit alike (not exactly the same as): Derangement Permutation Implementation using R Programming

The above C++ code implements the DP solution that runs at O(N) both in time and space.

Paint Fences/Walls

• Teaching Kids Programming - Paint Fences (No 3 Consecutive Same Colours) - Bottom Up Dynamic Programming Algorithm
• Compute the Number of Ways to Paint the House via Dynamic Programming Algorithm
• Teaching Kids Programming - Paint Fences (No 3 Consecutive Same Colours) - Top Down Dynamic Programming Algorithm (Recursion + Memoization)

–EOF (The Ultimate Computing & Technology Blog) —