number of adjacent 1 's can not exceed i-1
for ( int j = 0 ; j <= k ; j ++ ) { 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 ) dp [ i ] [ j ] [ 1 ] += dp [ i - 1 ] [ j - 1 ] [ 1 ] ; } } return dp [ n ] [ k ] [ 0 ] + dp [ n ] [ k ] [ 1 ] ; }