Prerequisites
Before attempting this problem, you should be comfortable with:
- Dynamic Programming Fundamentals - Understanding overlapping subproblems and optimal substructure
- Recurrence Relations - Deriving and implementing formulas that relate current state to previous states
- Memoization - Caching recursive results to avoid redundant computation
- Space Optimization - Reducing DP table to constant space when only previous states are needed
1. Top-Down Dynamic Programming (Recursion + Memoization)
Intuition
The constraint is that no more than two consecutive posts can have the same color. For each post, we can either paint it a different color from the previous post, or paint it the same color (but only if the two previous posts are different).
This leads to a recurrence: totalWays(i) = (k - 1) * (totalWays(i - 1) + totalWays(i - 2)). The first term handles painting post i differently from post i - 1 (k - 1 choices). The second term handles painting post i the same as post i - 1, which requires post i - 1 to be different from post i - 2.
Algorithm
- Define
totalWays(i)to return the number of valid ways to paint posts1throughi. - Base cases:
totalWays(1) = kandtotalWays(2) = k * k. - For
i > 2, use the recurrence:totalWays(i) = (k - 1) * (totalWays(i - 1) + totalWays(i - 2)). - Use memoization to cache results and avoid redundant computation.
- Return
totalWays(n).
class Solution:
def numWays(self, n: int, k: int) -> int:
def total_ways(i):
if i == 1:
return k
if i == 2:
return k * k
# Check if we have already calculated totalWays(i)
if i in memo:
return memo[i]
# Use the recurrence relation to calculate total_ways(i)
memo[i] = (k - 1) * (total_ways(i - 1) + total_ways(i - 2))
return memo[i]
memo = {}
return total_ways(n)Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the number of fence posts.
2. Bottom-Up Dynamic Programming (Tabulation)
Intuition
The same recurrence can be computed iteratively instead of recursively. We fill an array from the base cases up to n, which avoids recursion overhead and stack depth issues.
This approach is often more efficient in practice since it avoids function call overhead and naturally iterates through states in order.
Algorithm
- Handle base cases: if
nis1, returnk. Ifnis2, returnk * k. - Create an array
totalWaysof sizen + 1. - Set
totalWays[1] = kandtotalWays[2] = k * k. - For
ifrom3ton, computetotalWays[i] = (k - 1) * (totalWays[i - 1] + totalWays[i - 2]). - Return
totalWays[n].
class Solution:
def numWays(self, n: int, k: int) -> int:
# Base cases for the problem to avoid index out of bound issues
if n == 1:
return k
if n == 2:
return k * k
total_ways = [0] * (n + 1)
total_ways[1] = k
total_ways[2] = k * k
for i in range(3, n + 1):
total_ways[i] = (k - 1) * (total_ways[i - 1] + total_ways[i - 2])
return total_ways[n]Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the number of fence posts.
3. Bottom-Up, Constant Space
Intuition
Since the recurrence only depends on the previous two values, we do not need to store the entire array. We can use two variables to track totalWays(i - 1) and totalWays(i - 2), updating them as we iterate.
This optimization reduces space complexity from O(n) to O(1).
Algorithm
- If
nis1, returnk. - Initialize
twoPostsBack = kandonePostBack = k * k. - For
ifrom3ton:- Compute
curr = (k - 1) * (onePostBack + twoPostsBack). - Shift:
twoPostsBack = onePostBack,onePostBack = curr.
- Compute
- Return
onePostBack.
class Solution:
def numWays(self, n: int, k: int) -> int:
if n == 1:
return k
two_posts_back = k
one_post_back = k * k
for i in range(3, n + 1):
curr = (k - 1) * (one_post_back + two_posts_back)
two_posts_back = one_post_back
one_post_back = curr
return one_post_backTime & Space Complexity
- Time complexity:
- Space complexity: constant space
Where is the number of fence posts.
Common Pitfalls
Misunderstanding the Three Consecutive Constraint
The problem forbids more than two consecutive posts with the same color. Some solvers mistakenly interpret this as no two adjacent posts can share a color, which is too restrictive. Two adjacent posts can have the same color as long as there is not a third consecutive post with that same color.
Incorrect Base Cases for Small n
When n equals 1, there are exactly k ways. When n equals 2, there are k*k ways since any combination is valid (no three consecutive posts exist yet). Forgetting to handle these base cases or computing them incorrectly leads to wrong answers and potential index-out-of-bounds errors.
Deriving the Wrong Recurrence Relation
The recurrence totalWays(i) = (k-1) * (totalWays(i-1) + totalWays(i-2)) accounts for two scenarios: painting differently from the previous post, or painting the same as the previous post (which requires the two before that to be different). Confusing the logic of when same-color painting is allowed leads to an incorrect formula.