number of adjacent 1 's can not exceed i-1
for ( $ j = 0 ; $ j < $ i ; $ j ++ ) { if ( isset ( $ dp [ $ i ] [ $ j ] [ 0 ] ) || isset ( $ dp [ $ i ] [ $ j ] [ 1 ] ) ) { $ dp [ $ i ] [ $ j ] [ 0 ] = $ dp [ $ i - 1 ] [ $ j ] [ 0 ] + $ dp [ $ i - 1 ] [ $ j ] [ 1 ] ; $ dp [ $ i ] [ $ j ] [ 1 ] = $ dp [ $ i - 1 ] [ $ j ] [ 0 ] ; } if ( $ j - 1 >= 0 && isset ( $ dp [ $ i ] [ $ j ] [ 1 ] ) ) $ dp [ $ i ] [ $ j ] [ 1 ] += $ dp [ $ i - 1 ] [ $ j - 1 ] [ 1 ] ; } } return $ dp [ $ n ] [ $ k ] [ 0 ] + $ dp [ $ n ] [ $ k ] [ 1 ] ; }