Teaching Kids Programming – Paint Fences (No 3 Consecutive Same Colours) – Bottom Up Dynamic Programming Algorithm

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.

Paint Fences (No 3 Consecutive Same Colours) – Bottom Up Dynamic Programming Algorithm

We learned that in the last lesson the Dynamic Programming Equation: Teaching Kids Programming – Paint Fences (No 3 Consecutive Same Colours) – Top Down Dynamic Programming Algorithm (Recursion + Memoization)

There are two ways to paint the n-th (last) fence: paint it different colour than the (n-1)th fence, we have . And, if we paint it the same colour with the (n-1)th fence, we have . The f(n) is the sum of both terms.

Similar as Fibonacci numbers, we can implement this using bottom-up Dynamic Programming algorithm, using two variables a and b that iterates the process.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def numWays(self, n: int, k: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return k        
        a, b = k, k * k
        for i in range(3, n + 1):
            a, b = b, (k - 1) * (a + b)
        return b

class Solution:
    def numWays(self, n: int, k: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return k        
        a, b = k, k * k
        for i in range(3, n + 1):
            a, b = b, (k - 1) * (a + b)
        return b

The time complexity is O(N) and the space complexity is O(1) constant.

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