Python DP solution, O(n) run time, O(1) space


  • 3
    Y
    def numWays(self, n, k):
        if n == 0 or k == 0:
            return 0
            
        num_same = 0 # the number of ways that the last element has the same color as the second last one
        num_diff = k # the number of ways that the last element has differnt color from the second last one
        
        for i in range(1, n):
            total = num_diff + num_same
            num_same = num_diff
            num_diff = total * (k - 1)
        
        return num_same + num_diff

  • 0

    I don't why for the second case (different color from the 2nd last one) has k - 1 conditions not k?


  • 0
    M

    because for each number in the end, it has (k-1) number can make these two became diff in next round, and these combinations are all valid since they are diff


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.