[LeetCode] 276. Paint Fence

 Problem : https://leetcode.com/problems/paint-fence/

Similar to the climbing-stairs, we should think about the 'last state'.

When we paint the last fence, we either paint it with a different color or paint it with the same color as the last 2 fence.

class Solution:
    def numWays(self, n: int, k: int) -> int:
        end_with_diff_color = [0] * n
        end_with_same_color = [0] * n
        
        end_with_diff_color[0] = k
        
        for i in range(1, n):
            end_with_diff_color[i] = end_with_same_color[i-1] * (k-1) + end_with_diff_color[i-1] * (k-1)
            end_with_same_color[i] = end_with_diff_color[i-1]
            
        return end_with_diff_color[-1] + end_with_same_color[-1]

Because "i" state only dependes on the result of "i - 1" state. We can reduce the space complexity.

class Solution:
    def numWays(self, n: int, k: int) -> int:
        end_with_same_color, end_with_diff_color = 0, k
    
        for i in range(1, n):
            end_with_same_color, end_with_diff_color = end_with_diff_color, end_with_same_color * (k-1) + end_with_diff_color * (k-1)
                        
        return end_with_diff_color + end_with_same_color