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
< ? php function totalWays ( $ N , $ M , $ X ) { $ dp = array ( array ( ) ) ; if ( $ X == 1 ) { $ dp [ 0 ] [ 0 ] = 1 ; } else { $ dp [ 0 ] [ 1 ] = 0 ; } if ( $ X == 1 ) { $ dp [ 1 ] [ 0 ] = 0 ; $ dp [ 1 ] [ 1 ] = $ M - 1 ; } else { $ dp [ 1 ] [ 0 ] = 1 ; $ dp [ 1 ] [ 1 ] = ( $ M - 2 ) ; } for ( $ i = 2 ; $ i < $ N ; $ i ++ ) { $ dp [ $ i ] [ 0 ] = $ dp [ $ i - 1 ] [ 1 ] ; $ dp [ $ i ] [ 1 ] = $ dp [ $ i - 1 ] [ 0 ] * ( $ M - 1 ) + $ dp [ $ i - 1 ] [ 1 ] * ( $ M - 2 ) ; } return $ dp [ $ N - 1 ] [ 0 ] ; } $ N = 4 ; $ M = 3 ; $ X = 2 ; echo totalWays ( $ N , $ M , $ X ) ; ? >