Ways to fill N positions using M colors such that there are exactly K pairs of adjacent different colors | PHP implementation of the approach ; Recursive function to find the required number of ways ; When all positions are filled ; If adjacent pairs are exactly K ; If already calculated ; Next position filled with same color ; Next position filled with different color So there can be m - 1 different colors ; Driver Code
< ? php $ GLOBALS [ ' max ' ] = 4 ; function countWays ( $ index , $ cnt , $ dp , $ n , $ m , $ k ) { if ( $ index == $ n ) { if ( $ cnt == $ k ) return 1 ; else return 0 ; } if ( $ dp [ $ index ] [ $ cnt ] != -1 ) return $ dp [ $ index ] [ $ cnt ] ; $ ans = 0 ; $ ans += countWays ( $ index + 1 , $ cnt , $ dp , $ n , $ m , $ k ) ; $ ans += ( $ m - 1 ) * countWays ( $ index + 1 , $ cnt + 1 , $ dp , $ n , $ m , $ k ) ; $ dp [ $ index ] [ $ cnt ] = $ ans ; return $ dp [ $ index ] [ $ cnt ] ; } $ n = 3 ; $ m = 3 ; $ k = 2 ; $ dp = array ( array ( ) ) ; for ( $ i = 0 ; $ i < $ n + 1 ; $ i ++ ) for ( $ j = 0 ; $ j < $ GLOBALS [ ' max ' ] ; $ j ++ ) $ dp [ $ i ] [ $ j ] = -1 ; echo $ m * countWays ( 1 , 0 , $ dp , $ n , $ m , $ k ) ; ? >