## Challenge#

You are painting post on a fence of size N.
Only K consecutive post can have the same color.
Return the number of way you can paint the fence.

E.g:

``````N = 3
K = 2
-> will return 6
``````

## Solution 1 - Time Limted Exceeded#

``````class Solution:
def helper(self,n, k, fence) ->int:
if len(fence) >= 3 and fence[-3] == fence[-2] == fence[-1]:
return
if len(fence) == n:
self.count += 1
return
for i in range(0, k):
self.helper(n, k, fence + str(i))

def numWays(self, n: int, k: int) -> int:
self.count = 0
self.helper(n, k, "")
return self.count
``````

The code above will create a recursion tree like so:

``````            /         \
/           \
R             G
/  \           /  \
R     G         R     G
/ \   / \       / \    / \
R    G  R  G     R   G  R   G
------------------------------------
1  2  3     4   5  6
``````

Time complexity: k^n

## Solution 2 - Memoization#

``````class Solution:

def helper(self,n, k, parent, previous_same) ->int:
if (n, previous_same) in self.memo:
return self.memo[(n, previous_same)]
if n == 0:
return 1

ways = 0
for current in range(k):
if parent == current and previous_same:
continue
ways += self.helper(n-1, k, current, current == parent)
self.memo[(n,previous_same)] = ways
return ways

def numWays(self, n: int, k: int) -> int:
self.count = 0
self.memo = {}
res = self.helper(n, k, None, None)
return res
``````