Color N boxes using M colors such that K boxes have different color from the box on its left | PHP 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
< ? php $ M = 1001 ; $ MOD = 998244353 ; $ dp = array_fill ( 0 , $ M , array_fill ( 0 , $ M , -1 ) ) ; function solve ( $ idx , $ diff , $ N , $ M , $ K ) { global $ dp , $ MOD ; if ( $ idx > $ N ) { if ( $ diff == $ K ) return 1 ; return 0 ; } if ( $ dp [ $ idx ] [ $ diff ] != -1 ) return $ dp [ $ idx ] [ $ diff ] ; $ 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 ; } $ N = 3 ; $ M = 3 ; $ K = 0 ; echo ( $ M * solve ( 2 , 0 , $ N , $ M , $ K ) ) ; ? >