$ cat ./coding/276-paint-fence.md

────────────────────────────────────────────────────────────

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)

$ ls ./coding/ | grep -v 276-paint-fence