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
< ? php function countWays ( $ n , $ k ) { $ total = $ k ; $ mod = 1000000007 ; $ same = 0 ; $ diff = $ k ; for ( $ i = 2 ; $ i <= $ n ; $ i ++ ) { $ same = $ diff ; $ diff = $ total * ( $ k - 1 ) ; $ diff = $ diff % $ mod ; $ total = ( $ same + $ diff ) % $ mod ; } return $ total ; } $ n = 3 ; $ k = 2 ; echo countWays ( $ n , $ k ) . " STRNEWLINE " ; ? >