Color N boxes using M colors such that K boxes have different color from the box on its left | Python3 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
M = 1001 ; NEW_LINE MOD = 998244353 ; NEW_LINE dp = [ [ - 1 ] * M ] * M NEW_LINE def solve ( idx , diff , N , M , K ) : NEW_LINE INDENT if ( idx > N ) : NEW_LINE INDENT if ( diff == K ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT if ( dp [ idx ] [ diff ] != - 1 ) : NEW_LINE INDENT return dp [ idx ] ; NEW_LINE DEDENT ans = solve ( idx + 1 , diff , N , M , K ) ; NEW_LINE ans += ( M - 1 ) * solve ( idx + 1 , diff + 1 , N , M , K ) ; NEW_LINE dp [ idx ] [ diff ] = ans % MOD ; NEW_LINE return dp [ idx ] [ diff ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 3 NEW_LINE M = 3 NEW_LINE K = 0 NEW_LINE print ( M * solve ( 2 , 0 , N , M , K ) ) NEW_LINE DEDENT