Ways to fill N positions using M colors such that there are exactly K pairs of adjacent different colors | Python 3 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
max = 4 NEW_LINE def countWays ( index , cnt , dp , n , m , k ) : NEW_LINE INDENT if ( index == n ) : NEW_LINE INDENT if ( cnt == k ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT else : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT if ( dp [ index ] [ cnt ] != - 1 ) : NEW_LINE INDENT return dp [ index ] [ cnt ] NEW_LINE DEDENT ans = 0 NEW_LINE ans += countWays ( index + 1 , cnt , dp , n , m , k ) NEW_LINE ans += ( m - 1 ) * countWays ( index + 1 , cnt + 1 , dp , n , m , k ) NEW_LINE dp [ index ] [ cnt ] = ans NEW_LINE return dp [ index ] [ cnt ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 3 NEW_LINE m = 3 NEW_LINE k = 2 NEW_LINE dp = [ [ - 1 for x in range ( n + 1 ) ] for y in range ( max ) ] NEW_LINE print ( m * countWays ( 1 , 0 , dp , n , m , k ) ) NEW_LINE DEDENT