LeetCode #276: Paint Fence
β’ 56 words β’ 1 min β’ updated
python
class Solution:
def numWays(self, n: int, k: int) -> int:
from functools import cache
@cache
def solve(n):
if n <= 0:
return 0
if n == 1:
return k
if n == 2:
return k ** 2
return (k - 1) * (solve(n - 1) + solve(n - 2))
return solve(n)