Problem statement

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

Solution

Problem formulation is not clear: what is meant that there can not be three posts in a row with the same color, not what is stated. The idea is to have dp with two states: a means that last two posts painted in the same color and b means that they painted in different colors. Then we can update them in O(1).

Complexity

Time complexity is $O(n)$, space is $O(1)$.

Code

class Solution:
    def numWays(self, n, k):
        a, b = 0, k
        for i in range(n-1):
            a, b = b, (a + b)*(k - 1)
            
        return a + b