276. Paint Fence
class Solution:
def numWays(self, n: int, k: int) -> int:
memo = {}
def dfs(ways):
if ways == 1:
return k
if ways == 2:
return k * k
if ways not in memo:
memo[ways] = (k - 1) * (dfs(ways - 1) + dfs(ways - 2))
return memo[ways]
return dfs(n)