Mastering the Painting Fence Algorithm: A Deep Dive into Dynamic Programming

As a senior software engineer with expertise in a wide range of programming languages and technologies, I‘m excited to share my insights on the Painting Fence Algorithm, a classic problem in computer science that showcases the power of dynamic programming.

Understanding the Painting Fence Problem

The Painting Fence problem can be stated as follows: Given a fence with n posts and k colors, find the number of ways to paint the fence such that no more than two consecutive posts have the same color.

This problem has a wide range of applications in various domains, from software engineering and data analysis to problem-solving and algorithm design. By understanding the Painting Fence Algorithm, you‘ll gain valuable insights into the principles of dynamic programming, which is a fundamental technique for solving complex problems efficiently.

Recursive Approach

The most straightforward approach to solving the Painting Fence problem is to use a recursive solution. The idea is to define the solution in terms of two choices: painting the last post a different color from the previous one or painting the last two posts the same color.

The recurrence relation for the recursive solution can be expressed as:

countWays(n) = countWays(n-1)*(k-1) + countWays(n-2)*(k-1)

Here, countWays(n) represents the number of ways to paint a fence with n posts and k colors.

The base cases for this recursive solution are:

  • If n == 1, there are k ways to paint the first post.
  • If n == 2, there are k * k ways to paint the two posts.

Let‘s take a look at the implementation of the recursive solution in various programming languages:

C++
#include <bits/stdc++.h>
using namespace std;

// Returns count of ways to color k posts
int countWays(int n, int k) {
    // base cases
    if (n == 1) return k;
    if (n == 2) return k * k;

    // Ways in which last fence is of different color.
    int cnt1 = countWays(n - 1, k) * (k - 1);

    // Ways in which last 2 fences are of same color.
    int cnt2 = countWays(n - 2, k) * (k - 1);

    return cnt1 + cnt2;
}

int main() {
    int n = 3, k = 2;
    cout << countWays(n, k) << endl;
    return 0;
}
Java
class GfG {
    // Returns count of ways to color k posts
    static int countWays(int n, int k) {
        // base cases
        if (n == 1) return k;
        if (n == 2) return k * k;

        // Ways in which last fence is of different color.
        int cnt1 = countWays(n - 1, k) * (k - 1);

        // Ways in which last 2 fences are of same color.
        int cnt2 = countWays(n - 2, k) * (k - 1);

        return cnt1 + cnt2;
    }

    public static void main(String[] args) {
        int n = 3, k = 2;
        System.out.println(countWays(n, k));
    }
}
Python
# Returns count of ways to color k posts
def countWays(n, k):
    # base cases
    if n == 1:
        return k
    if n == 2:
        return k * k

    # Ways in which last fence is of different color.
    cnt1 = countWays(n - 1, k) * (k - 1)

    # Ways in which last 2 fences are of same color.
    cnt2 = countWays(n - 2, k) * (k - 1)

    return cnt1 + cnt2

if __name__ == "__main__":
    n = 3
    k = 2
    print(countWays(n, k))

The time complexity of the recursive solution is O(2^n), as the algorithm makes an exponential number of recursive calls. The space complexity is O(n) due to the recursive call stack.

While the recursive solution is straightforward, it suffers from the problem of overlapping subproblems, where certain subproblems are computed multiple times, leading to inefficient computation. To optimize this, we can use a dynamic programming approach.

Top-Down Dynamic Programming (Memoization)

The top-down dynamic programming, also known as memoization, is a technique that helps to avoid redundant computations by storing the results of previously computed subproblems in a data structure, such as an array or a hash table, and reusing them whenever the same subproblem is encountered again.

The memoization approach can be implemented as follows:

C++
#include <bits/stdc++.h>
using namespace std;

int countWaysRecur(int n, int k, vector<int> &memo) {
    // base cases
    if (n == 1) return k;
    if (n == 2) return k * k;

    if (memo[n] != -1) return memo[n];

    // Ways in which last fence is of different color.
    int cnt1 = countWaysRecur(n - 1, k, memo) * (k - 1);

    // Ways in which last 2 fences are of same color.
    int cnt2 = countWaysRecur(n - 2, k, memo) * (k - 1);

    return memo[n] = cnt1 + cnt2;
}

// Returns count of ways to color k posts
int countWays(int n, int k) {
    vector<int> memo(n + 1, -1);
    return countWaysRecur(n, k, memo);
}

int main() {
    int n = 3, k = 2;
    cout << countWays(n, k) << endl;
    return 0;
}
Java
class GfG {
    static int countWaysRecur(int n, int k, int[] memo) {
        // base cases
        if (n == 1) return k;
        if (n == 2) return k * k;

        if (memo[n] != -1) return memo[n];

        // Ways in which last fence is of different color.
        int cnt1 = countWaysRecur(n - 1, k, memo) * (k - 1);

        // Ways in which last 2 fences are of same color.
        int cnt2 = countWaysRecur(n - 2, k, memo) * (k - 1);

        return memo[n] = cnt1 + cnt2;
    }

    // Returns count of ways to color k posts
    static int countWays(int n, int k) {
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return countWaysRecur(n, k, memo);
    }

    public static void main(String[] args) {
        int n = 3, k = 2;
        System.out.println(countWays(n, k));
    }
}
Python
def countWaysRecur(n, k, memo):
    # base cases
    if n == 1:
        return k
    if n == 2:
        return k * k

    if memo[n] != -1:
        return memo[n]

    # Ways in which last fence is of different color.
    cnt1 = countWaysRecur(n - 1, k, memo) * (k - 1)

    # Ways in which last 2 fences are of same color.
    cnt2 = countWaysRecur(n - 2, k, memo) * (k - 1)

    memo[n] = cnt1 + cnt2
    return memo[n]

# Returns count of ways to color k posts
def countWays(n, k):
    memo = [-1] * (n + 1)
    return countWaysRecur(n, k, memo)

if __name__ == "__main__":
    n = 3
    k = 2
    print(countWays(n, k))

The memoization approach has a time complexity of O(n) and a space complexity of O(n), as it stores the results of previously computed subproblems in a 1D array.

Bottom-Up Dynamic Programming (Tabulation)

Another way to solve the Painting Fence problem is to use a bottom-up dynamic programming approach, also known as tabulation. In this approach, we start with the base cases and gradually build up the solution for larger subproblems.

The tabulation solution can be implemented as follows:

C++
#include <bits/stdc++.h>
using namespace std;

// Returns count of ways to color k posts
int countWays(int n, int k) {
    // base cases
    if (n == 1) return k;
    if (n == 2) return k * k;

    vector<int> dp(n + 1);

    // Fill value for 1 and 2 fences
    dp[1] = k;
    dp[2] = k * k;

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] * (k - 1) + dp[i - 2] * (k - 1);
    }

    return dp[n];
}

int main() {
    int n = 3, k = 2;
    cout << countWays(n, k) << endl;
    return 0;
}
Java
class GfG {
    // Returns count of ways to color k posts
    static int countWays(int n, int k) {
        // base cases
        if (n == 1) return k;
        if (n == 2) return k * k;

        int[] dp = new int[n + 1];

        // Fill value for 1 and 2 fences
        dp[1] = k;
        dp[2] = k * k;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] * (k - 1) + dp[i - 2] * (k - 1);
        }

        return dp[n];
    }

    public static void main(String[] args) {
        int n = 3, k = 2;
        System.out.println(countWays(n, k));
    }
}
Python
def countWays(n, k):
    # base cases
    if n == 1:
        return k
    if n == 2:
        return k * k

    dp = [0] * (n + 1)

    # Fill value for 1 and 2 fences
    dp[1] = k
    dp[2] = k * k

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] * (k - 1) + dp[i - 2] * (k - 1)

    return dp[n]

if __name__ == "__main__":
    n = 3
    k = 2
    print(countWays(n, k))

The tabulation approach has a time complexity of O(n) and a space complexity of O(n), as it uses a 1D array to store the intermediate results.

Space-Optimized Dynamic Programming

While the tabulation approach is more efficient than the recursive solution, it still requires O(n) space to store the intermediate results. We can further optimize the space complexity by observing that we only need to keep track of the last two computed values to calculate the current value.

The space-optimized solution can be implemented as follows:

C++
#include <bits/stdc++.h>
using namespace std;

// Returns count of ways to color k posts
int countWays(int n, int k) {
    // base cases
    if (n == 1) return k;
    if (n == 2) return k * k;

    // Fill value for 1 and 2 fences
    int prev2 = k;
    int prev1 = k * k;

    for (int i = 3; i <= n; i++) {
        int curr = prev1 * (k - 1) + prev2 * (k - 1);

        // update the values
        prev2 = prev1;
        prev1 = curr;
    }

    return prev1;
}

int main() {
    int n = 3, k = 2;
    cout << countWays(n, k) << endl;
    return 0;
}
Java
class GfG {
    // Returns count of ways to color k posts
    static int countWays(int n, int k) {
        // base cases
        if (n == 1) return k;
        if (n == 2) return k * k;

        // Fill value for 1 and 2 fences
        int prev2 = k;
        int prev1 = k * k;

        for (int i = 3; i <= n; i++) {
            int curr = prev1 * (k - 1) + prev2 * (k - 1);

            // update the values
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }

    public static void main(String[] args) {
        int n = 3, k = 2;
        System.out.println(countWays(n, k));
    }
}
Python

def countWays(n, k):
    # base cases
    if n == 1:
        return k
    if n == 2:
        return k *

Read More,

Leave a Reply

Your email address will not be published. Required fields are marked *