Painting Fence Algorithm in Python

Given a fence with n posts and k colors, find out the number of ways of painting the fence such that at most 2 adjacent posts have the same color. Since the answer can be large, return it modulo 10^9 + 7.

Input : n = 2 k = 4
Output : 16
Explanation: We have 4 colors and 2 posts.
Ways when both posts have same color : 4
Ways when both posts have diff color :4(choices for 1st post) * 3(choices for 2nd post) = 12

Input : n = 3 k = 2
Output : 6

What is a Painting Fence Algorithm?

The Painting Fence algorithm addresses a common combinatorial problem: Given a fence with n posts, how many ways can you paint the fence with k colors such that no more than two adjacent posts have the same color? This problem can be easily solved using Dynamic Programming.

Algorithm:

• Create an array dp of size n+1 to store the number of ways to paint the fence for each number of posts.
• Define mod as 1000000007 to handle large numbers.
• dp[1] = k: If there is only one post, it can be painted in k ways.
• dp[2] = k * k: If there are two posts, there are k * k ways to paint them because each post can be painted independently with any of the k colors.
• Iterate from i = 3 to i = n:
  • Use the formula: dp[i] = ((k - 1) * (dp[i - 1] + dp[i - 2])) % mod to calculate the number of ways to paint i posts:
    • (k - 1): The current post can be painted in any of the k - 1 colors different from the previous one.
    • (dp[i - 1] + dp[i - 2]): Add the ways to paint the previous post configurations.
• The number of ways to paint n posts is found in dp[n].

Below is the implementation of the above algorithm:

# Python3 program for Painting Fence Algorithm  # optimised version # Returns count of ways to color k posts  def countWays(n, k): dp = [0] * (n + 1) total = k mod = 1000000007 dp[1] = k dp[2] = k * k for i in range(3,n+1): dp[i] = ((k - 1) * (dp[i - 1] + dp[i - 2])) % mod return dp[n] # Driver code  n = 3 k = 2 print(countWays(n, k)) # This code is contributed by shubhamsingh10 

6 

Time Complexity: O(N)
Auxiliary Space: O (N)

Painting Fence Algorithm in Python (Space Optimized):

We can optimize the above solution by use one variable instead of a table.

Below is the implementation of the problem:

# Python3 program for Painting  # Fence Algorithm  # Returns count of ways to color k posts using k colors  def countWays(n, k) : # There are k ways to color first post  total = k mod = 1000000007 # There are 0 ways for single post to  # violate (same color_ and k ways to  # not violate (different color)  same, diff = 0, k # Fill for 2 posts onwards  for i in range(2, n + 1): # Current same is same as previous diff  same = diff # We always have k-1 choices for next post  diff = (total * ((k - 1) % mod)) % mod # Total choices till i.  total = (same + diff) % mod return total # Driver code  if __name__ == "__main__" : n, k = 3, 2 print(countWays(n, k)) # This code is contributed by @nibeditans 

6 

Time Complexity: O(N)
Auxiliary Space: O(1)