Paint Fence - Leetcode Solution

Paint Fence is a dynamic programming problem on LeetCode. The problem statement can be paraphrased 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.

To solve this problem, we can use dynamic programming. We will define an array dp where dp[i] represents the number of ways to paint the first i posts. We will also define two variables, same and diff, which represent the number of ways to paint the last two posts the same color or different colors, respectively.

At each iteration, we will use the following recurrence relations:

• If we paint the ith post the same color as the (i-1)th post, then the number of ways to paint the first i posts is dp[i-1] * same.
• If we paint the ith post a different color than the (i-1)th post, then the number of ways to paint the first i posts is dp[i-1] * diff.

We can initialize our variables as follows:

• same = k (since we can paint the first two posts any color)
• diff = k * (k-1) (since we can paint the first two posts any two different colors)
• dp[0] = 0 (there are no ways to paint zero posts)
• dp[1] = k (there are k ways to paint one post)

We can then fill in the rest of the dp array by iterating from 2 to n and using the recurrence relations. At the end, we return dp[n].

Here's the Python implementation of the solution:

def numWays(n: int, k: int) -> int: if n == 0: return 0 if n == 1: return k

same = k
diff = k * (k-1)
dp = [0] * (n+1)
dp[1] = k

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

return dp[n]

1