# 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 <= 50`
• `1 <= 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 = k;
numWays = 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+1` spaces 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.