Number of ways to form an array with distinct adjacent elements | Returns the total ways to form arrays such that every consecutive element is different and each element except the first and last can take values from 1 to M ; define the dp [ ] [ ] array ; if the first element is 1 ; there is only one way to place a 1 at the first index ; the value at first index needs to be 1 , thus there is no way to place a non - one integer ; if the first element was 1 then at index 1 , only non one integer can be placed thus there are M - 1 ways to place a non one integer at index 2 and 0 ways to place a 1 at the 2 nd index ; Else there is one way to place a one at index 2 and if a non one needs to be placed here , there are ( M - 2 ) options , i . e neither the element at this index should be 1 , neither should it be equal to the previous element ; Build the dp array in bottom up manner ; f ( i , one ) = f ( i - 1 , non - one ) ; f ( i , non - one ) = f ( i - 1 , one ) * ( M - 1 ) + f ( i - 1 , non - one ) * ( M - 2 ) ; last element needs to be one , so return dp [ n - 1 ] [ 0 ] ; Driver Code
def totalWays ( N , M , X ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( 2 ) ] for j in range ( N + 1 ) ] NEW_LINE if ( X == 1 ) : NEW_LINE INDENT dp [ 0 ] [ 0 ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 0 ] [ 1 ] = 0 NEW_LINE DEDENT if ( X == 1 ) : NEW_LINE INDENT dp [ 1 ] [ 0 ] = 0 NEW_LINE dp [ 1 ] [ 1 ] = M - 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 1 ] [ 0 ] = 1 NEW_LINE dp [ 1 ] [ 1 ] = ( M - 2 ) NEW_LINE DEDENT for i in range ( 2 , N ) : NEW_LINE INDENT dp [ i ] [ 0 ] = dp [ i - 1 ] [ 1 ] NEW_LINE dp [ i ] [ 1 ] = dp [ i - 1 ] [ 0 ] * ( M - 1 ) + dp [ i - 1 ] [ 1 ] * ( M - 2 ) NEW_LINE DEDENT return dp [ N - 1 ] [ 0 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 4 NEW_LINE M = 3 NEW_LINE X = 2 NEW_LINE print ( totalWays ( N , M , X ) ) NEW_LINE DEDENT