Ways to fill N positions using M colors such that there are exactly K pairs of adjacent different colors | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define max  4 NEW_LINE int countWays ( int index , int cnt , int dp [ ] [ max ] , 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 ; } int main ( ) { int n = 3 , m = 3 , k = 2 ; int dp [ n + 1 ] [ max ] ; memset ( dp , -1 , sizeof dp ) ; cout << m * countWays ( 1 , 0 , dp , n , m , k ) ; }