Teaching Kids Programming – Paint Fences (No 3 Consecutive Same Colours) – Top Down Dynamic Programming Algorithm (Recursion + Memoization)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Paint Fences/Walls – using Dynamic Programming Algorithms

Example 1:
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^5
The testcases are generated such that the answer is in the range [0, 231 – 1] for the given n and k.

Count How Many Ways to Paint the Fences with No Same Colours for 3 Consecutive Walls using Top Down Dynamic Programming Algorithm (Recursion with Memoization)

Let’s use f(n) to represent the number of the ways to paint the n walls with no same colours for any consecutive walls. We know the base cases: when n is zero, the answer is zero. When there is only one wall, we can paint it with k colours, when there are two walls, there is k*k (multiplication rule) choices to paint.

When there are more than 2 walls, we have to look at the last wall specificially. We have certainly two choices:

• Paint the last wall with different colour than the second last: we have k-1 colours to choose from as long as it is different than the second last. The total solutions is (k-1)*f(n-1)
• Paint the last wall with the same colour as the second last, however, in this case, the second last should be different as the third last, which is (k-1)*f(n-2)

Add these two terms up we have the Dynamic Programming Equation to solve f(n):

Note that when k is 2, the DP equation is quite similar to Fibonacci Numbers expect the first 3 values.

Therefore, the complete Python code to solve this puzzle using the Top Down Dynamic Programming Algorithm a.k.a Recursion with Memoization technique:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def numWays(self, n: int, k: int) -> int:
        @cache
        def f(n):
            if n == 0:
                return 0
            if n == 1:
                return k
            if n == 2:
                return k * k
            return (k - 1) * (f(n - 1) + f(n - 2))
        return f(n)

class Solution:
    def numWays(self, n: int, k: int) -> int:
        @cache
        def f(n):
            if n == 0:
                return 0
            if n == 1:
                return k
            if n == 2:
                return k * k
            return (k - 1) * (f(n - 1) + f(n - 2))
        return f(n)

The time/space complexity is O(N) where N is the number of the walls/fences. There are N values/states i.e. f(N), and we only calculate once for each f(N) and the value is stored in the cache aka the Hash Map.

We can also solve this using the Bottom Up Dynamic Programming Approach (iteration).

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) —