Computing f ( i ) for each 2 <= i <= n .
for ( $ i = 2 ; $ i < $ n ; $ i ++ ) $ dp [ $ i ] = ( $ k - 2 ) * $ dp [ $ i - 1 ] + ( $ k - 1 ) * $ dp [ $ i - 2 ] ; return ( $ x == 1 ? ( $ k - 1 ) * $ dp [ $ n - 2 ] : $ dp [ $ n - 1 ] ) ; }