Irrespective of the LSB , dp [ 0 ] [ 1 ] is always 1 as there is always the need of making the suffix of the binary string of the form "11 . . . . 1" as suggested by the definition of dp [ i ] [ 1 ]
dp [ 0 ] [ 1 ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) { if ( S [ i ] == '0' ) {