Color N boxes using M colors such that K boxes have different color from the box on its left | CPP Program to Paint N boxes using M colors such that K boxes have color different from color of box on its left ; This function returns the required number of ways where idx is the current index and diff is number of boxes having different color from box on its left ; Base Case ; If already computed ; Either paint with same color as previous one ; Or paint with remaining ( M - 1 ) colors ; Driver code ; Multiply M since first box can be painted with any of the M colors and start solving from 2 nd box
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int M = 1001 ; const int MOD = 998244353 ; int dp [ M ] [ M ] ; int solve ( int idx , int diff , int N , int M , int K ) { if ( idx > N ) { if ( diff == K ) return 1 ; return 0 ; } if ( dp [ idx ] [ diff ] != -1 ) return dp [ idx ] [ diff ] ; int ans = solve ( idx + 1 , diff , N , M , K ) ; ans += ( M - 1 ) * solve ( idx + 1 , diff + 1 , N , M , K ) ; return dp [ idx ] [ diff ] = ans % MOD ; } int main ( ) { int N = 3 , M = 3 , K = 0 ; memset ( dp , -1 , sizeof ( dp ) ) ; cout << ( M * solve ( 2 , 0 , N , M , K ) ) << endl ; return 0 ; }