Ways to fill N positions using M colors such that there are exactly K pairs of adjacent different colors | Javascript 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
let 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 ] ; let ans = 0 ; ans += countWays ( index + 1 , cnt , dp , n , m , k ) ; ans += ( m - 1 ) * countWays ( index + 1 , cnt + 1 , dp , n , m , k ) ; return dp [ index ] [ cnt ] = ans ; } let n = 3 , m = 3 , k = 2 ; let dp = new Array ( n + 1 ) ; for ( let i = 0 ; i < n + 1 ; i ++ ) { dp [ i ] = new Array ( max ) ; for ( let j = 0 ; j < max ; j ++ ) dp [ i ] [ j ] = - 1 ; } document . write ( m * countWays ( 1 , 0 , dp , n , m , k ) ) ;