Painting Fence Algorithm | Returns count of ways to color k posts using k colors ; There are k ways to color first post ; There are 0 ways for single post to violate ( same color_ and k ways to not violate ( different color ) ; Fill for 2 posts onwards ; Current same is same as previous diff ; We always have k - 1 choices for next post ; Total choices till i . ; Driver code
def countWays ( n , k ) : NEW_LINE INDENT total = k NEW_LINE mod = 1000000007 NEW_LINE same , diff = 0 , k NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT same = diff NEW_LINE diff = total * ( k - 1 ) NEW_LINE diff = diff % mod NEW_LINE total = ( same + diff ) % mod NEW_LINE DEDENT return total NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n , k = 3 , 2 NEW_LINE print ( countWays ( n , k ) ) NEW_LINE DEDENT