DP approach to find current state with the help of previous state .
for ( int i = 1 ; i < n ; i ++ ) { dp [ i ] [ 0 ] = dp [ i - 1 ] [ 1 ] ; dp [ i ] [ 1 ] = ( dp [ i - 1 ] [ 0 ] * ( k - 1 ) ) + ( dp [ i - 1 ] [ 1 ] * ( k - 2 ) ) ; } System . out . println ( dp [ n - 1 ] [ 0 ] ) ; }