Paint Fence
Problem
We have to paint fence consists of n posts with k different colors with below rules:
- Every post must be painted with one and only one color
- Three or more consecutive posts cannot be painted with the same color
Our task is to find the number of ways to paint the fence.
For example,
Input: n = 3, k = 2 Output: 6
Input: n = 1, k = 1 Output: 1
Input: n = 7, k = 2 Output: 42
Constraints:
1 <= n <= 501 <= k <= 105
Solution
Brute Force
public int NumWays(int n, int k)
{
return NumWays(n);
int NumWays(int n)
{
if (n == 1)
return k;
if (n == 2)
return k * k;
return (k - 1) * (NumWays(n - 1) + NumWays(n - 2));
}
}
Complexity Analysis
- Time Complexity: At each step we generate two subtree and the height of the tree is
n. The total number of generated nodes is 2n. Since, we traverse all the nodes, then the complexity will be O(2n). - Space Complexity: The complexity will be the same with O(recursion depth), thus it will be O(n).
Top-down Dynamic Programming
public int NumWays(int n, int k)
{
Dictionary<int, int> memo = new Dictionary<int, int>();
return NumWays(n);
int NumWays(int n)
{
if (n == 1)
return k;
if (n == 2)
return k * k;
if (memo.ContainsKey(n))
{
return memo[n];
}
memo.Add(n, (k - 1) * (NumWays(n - 1) + NumWays(n - 2)));
return memo[n];
}
}
Complexity Analysis
- Time Complexity: Since we cache each
NumWays(n), then we will perform at most n recursive calls, thus the complexity is O(n). - Space Complexity: The complexity will be the same with O(recursion depth), thus it will be O(n).
Bottom-up Dynamic Programming
public int NumWays(int n, int k)
{
if (n == 1)
return k;
if (n == 2)
return k * k;
int[] numWays = new int[n + 1];
numWays[1] = k;
numWays[2] = k * k;
for (int i = 3; i <= n; i++)
{
numWays[i] = (k - 1) * (numWays[i - 1] + numWays[i - 2]);
}
return numWays[n];
}
Complexity Analysis
- Time Complexity: Since we iterate linearly up to
n, then the complexity is O(n). - Space Complexity: O(n) since we allocate
n+1spaces for caching (tabulation).
Bottom-up Dynamic Programming, Constant Space
public int NumWays(int n, int k)
{
if (n == 1) return k;
int twoPostsBack = k;
int onePostBack = k * k;
for (int i = 3; i <= n; i++)
{
int curr = (k - 1) * (onePostBack + twoPostsBack);
twoPostsBack = onePostBack;
onePostBack = curr;
}
return onePostBack;
}
Complexity Analysis
- Time Complexity: Since we iterate linearly up to
n, then the complexity is O(n). - Space Complexity: O(1) since we can replace the array with two variables to track previous results.