Problem Description

We are given a task to paint a fence that has n posts. Each post can be painted in any k colors. However, while painting, we need to follow a rule. The rule states that no more than two adjacent posts should have the same color.

The task is to find out all the possible ways to paint the fence with the given k colors following the rule. This problem can be approached using the dynamic programming concept. But first, we need to handle some border conditions. Here they are:

• If n is 0, it means there are no posts to paint, so return 0
• If n is 1, it means there is only one post to paint, so it can be painted in any of the k colors
• If n is 2, it means there are two posts which can be painted independently in any of the k colors.

Let's walk through a small example to better understand the problem,

For example, when n = 3 (We are given 3 posts to paint) and k = 2 (We can paint in any of the two available colors), we have 6 possible ways to paint the fence.

Let's represent Color1 as c1 and Color2 as c2. Below is the list of all possibilities.

1
2
3post1  post2  post3
4c1     c1     c2
5c1     c2     c1
6c1     c2     c2
7c2     c1     c1 
8c2     c1     c2
9c2     c2     c1

Solution Explanation

We use dynamic programming to solve this problem. First, we create a 1-dimensional dynamic programming table, named dp, with a size of n + 1 to store all the possible ways to paint n posts.

Here is how we fill up the table:

1. Fill up the border conditions (i.e., dp[0], dp[1], and dp[2]) first, as we already mentioned above.

• dp[0] = 0
• dp[1] = k
• dp[2] = k * k

2. Start from i = 3, for each i, the total number of ways (dp[i]) to paint i posts is equal to the sum of the total number of ways to paint i - 1 posts and i - 2 posts multiplied by k - 1.

Here is the formula to fill up the table:

dp[i] = (dp[i - 1] + dp[i - 2]) * (k - 1)

3. After filling up the table, return dp[n] which is the total number of ways to paint n posts.

Python Solution

1
2python
3class Solution:
4    def numWays(self, n: int, k: int) -> int:
5        if n == 0: 
6            return 0
7        if n == 1: 
8            return k
9        if n == 2: 
10            return k * k
11
12        dp = [0] * (n + 1)  # Creating a (n+1) sized and initialized array with 0 
13        dp[0] = 0
14        dp[1] = k
15        dp[2] = k * k
16
17        for i in range(3, n + 1):
18            dp[i] = (dp[i - 1] + dp[i - 2]) * (k - 1)
19
20        return dp[n]

Java Solution

1
2java
3class Solution {
4    public int numWays(int n, int k) {
5        if(n == 0)
6            return 0;
7        if(n == 1)
8            return k;
9        if(n == 2)
10            return k * k;
11
12        int dp[] = new int[n + 1];  // Allocation of memory with (n+1)
13        dp[0] = 0;
14        dp[1] = k;
15        dp[2] = k * k;
16
17        for(int i = 3; i <= n; i++)
18            dp[i] = (dp[i - 1] + dp[i - 2]) * (k - 1);
19
20        return dp[n];
21    }
22}

JavaScript Solution

1
2javascript
3var numWays = function(n, k) {
4    if (n === 0) 
5        return 0;
6    if (n === 1)
7        return k;
8    if (n === 2)
9        return k * k;
10
11    let dp = new Array(n+1);  // Creating a new array with (n+1) array
12    dp[0] = 0;
13    dp[1] = k;
14    dp[2] = k * k;
15
16    for(let i = 3; i <= n; i++)
17        dp[i] = (dp[i - 1] + dp[i - 2]) * (k - 1);
18
19    return dp[n];
20}

C++ Solution

1
2cpp
3class Solution {
4    public:
5      int numWays(int n, int k) {
6        if (n == 0)
7          return 0;
8        if (n == 1)
9          return k;
10        if (n == 2)
11          return k * k;
12          
13        vector<int> dp(n + 1, 0);  // Creating a vector of size (n+1) and initializing it to zero
14        dp[0] = 0;
15        dp[1] = k;
16        dp[2] = k * k;
17    
18        for (int i = 3; i <= n; ++i)
19          dp[i] = (dp[i - 1] + dp[i - 2]) * (k - 1);
20    
21        return dp[n];
22      }
23};

C# Solution

1
2csharp
3public class Solution {
4    public int NumWays(int n, int k) {
5        if (n == 0)
6          return 0;
7        if (n == 1)
8          return k;
9        if (n == 2)
10          return k * k;
11      
12        int[] dp = new int[n + 1];  // Creating array of size (n+1)
13        dp[0] = 0;
14        dp[1] = k;
15        dp[2] = k * k;
16    
17        for (int i = 3; i <= n; ++i)
18          dp[i] = (dp[i - 1] + dp[i - 2]) * (k - 1);
19    
20        return dp[n];
21    }
22}

We have two colors and 3 fence posts we can paint. No two fench posts next to each other can be the same color. So the last post would have k-1 colors to choose from, the post before this can have either same color as the one next to it or any of the remaining 'k-1' colors. We memoize this relation and after iterating over all 'n' fence posts return the total number of combinations we can paint 'n' fence posts with.

The relation we use for calculation is dp[i] = (dp[i - 1] + dp[i - 2]) * (k - 1).The dp[i - 1] represents the last post is painted in a different color compared to the second last post. So the total number of combinations in this case is the total number of combinations for last post times the total color choices left which is 'k-1'.

The dp[i - 2] represents the last post is painted in the same color as the second last post. So we have to make sure the last and the second last posts are painted in different colors compared to the third last post. So here the total number of combinations is the total combinations for the third last post times the total color choices left which is 'k-1'.

Finally, the total combinations for 'i' posts would be the sum of above two cases.

All of the solutions have a time complexity of O(n) since all posts till 'n' are iterated once. The space complexity for all solutions is O(n + 1)~= O(n) for dynamic programming array.

This problem was a basic demonstration of dynamic programming's power. Similar techniques can be applied to tackle more complex problems like painting a fence in such a way that no three fence posts are painted with the same color. As the conditions and extensions to a problem increase, dynamic programming becomes more and more useful.

In such a case, we will extend our formula to dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) * (k - 1). Here dp[i - 3] is added because we cannot have any three consecutive posts with the same color.

Overall, by capturing optimal substructure (dividing problems into smaller independent sub-problems) and overlapping sub-problems (solving every sub-problem only once by storing it), we perform an efficient search in the problem space. We start solving the sub-problems starting from the bottom up (from smaller to larger problems) which helps in making sure that the sub-problems are solved before solving the problem. This means that dynamic programming is generally used for optimization problems.