276. Paint Fence
class Solution:
def numWays(self, n: int, k: int) -> int:
@cache
def dfs(ways):
if ways == 1:
return k
if ways == 2:
return k * k
return (k - 1) * (dfs(ways - 1) + dfs(ways - 2))
return dfs(n)