Ways to fill N positions using M colors such that there are exactly K pairs of adjacent different colors | Java 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
class solution { static final int max = 4 ; static int countWays ( int index , int cnt , int dp [ ] [ ] , int n , int m , int k ) { if ( index == n ) { if ( cnt == k ) return 1 ; else return 0 ; } if ( dp [ index ] [ cnt ] != - 1 ) return dp [ index ] [ cnt ] ; int 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 ; } public static void main ( String args [ ] ) { int n = 3 , m = 3 , k = 2 ; int dp [ ] [ ] = new int [ n + 1 ] [ max ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) for ( int j = 0 ; j < max ; j ++ ) dp [ i ] [ j ] = - 1 ; System . out . println ( m * countWays ( 1 , 0 , dp , n , m , k ) ) ; } }