Paint Fences

lint code:https://www.lintcode.com/problem/514/description
class Solution:
    """
    @param n: non-negative integer, n posts
    @param k: non-negative integer, k colors
    @return: an integer, the total number of ways
    """
    def num_ways(self, n: int, k: int) -> int:
        if n==1:return k
        same=k
        diff=k*(k-1)
        total=same+diff
        for i in range(3,n+1):
            same=diff*1
            diff=total*(k-1)
            total=same+diff
        return total