# Python solution with detailed explanation

• Solution

Memoization

• The recursion tree is shown here: https://goo.gl/photos/ujNNfVvcphpBhKgXA
• Standard backtracking - use so_far to track the path and use it to pick the next candidates such that no three houses are painted same.
• Throw in a cache to get memoization done
• Improve it - you do not need entire path but just last two.
``````from collections import defaultdict
class Solution(object):
def ways(self, i, n, k, so_far, cache):
if len(so_far) == n:
return 1
else:
is_same = len(so_far)>=2 and so_far[-1] == so_far[-2]
if i in cache and is_same in cache[i]:
return cache[i][is_same]
cache[i][is_same] = 0
for j in range(k):
if is_same and so_far[-1] == j:
continue
so_far.append(j)
cache[i][is_same] += self.ways(i+1, n, k, so_far, cache)
so_far.pop()
return cache[i][is_same]

def numWays(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
# https://goo.gl/photos/ujNNfVvcphpBhKgXA
if n == 0 or k == 0:
return 0
cache = defaultdict(dict)
return self.ways(0, n, k, [], cache)
``````

https://discuss.leetcode.com/topic/30569/explanation-of-dp-o-n-time-complexity-o-1-space-complexity/3

Dynamic Programming

``````class Solution(object):
def numWays(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
if k == 0 or n == 0:
return 0
if n == 1:
return k
ways, fdiff = k*k, (k*k)-k
for i in range(3, n+1):
x = (k-1)*ways + fdiff
fdiff = (k-1)*ways
ways = x
return ways
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.