• Consider the following cases
• The last post is different in color with the second last
• (k - 1) * P(n - 1)
• Is the same color, which mean the third last is different
• 1 * (k - 1) * P(n - 2)

Question

Code

class Solution:
    def numWays(self, n: int, k: int) -> int:
        
        # 1, k
        # 2, k^2
        # 3, k * (k^2 - 0)
        # ...
        # n = (k - 1) * (P(n - 1) + P(n - 2))


        # Consider the following cases
        # The last post is different in color with the second last
        #   (k - 1) * P(n - 1)
        # Is the same color, which mean the third last is different
        # 1 * (k - 1) * P(n - 2)

        memo = {}

        def total_ways(x):
            if x == 1:
                return k

            if x == 2:
                return k * k 

            if x in memo:
                return memo[x]


            memo[x] = ((k - 1) * (total_ways(x - 1) + total_ways(x - 2)))

            return memo[x]
        
        return total_ways(n)