text: dp2 [ i ] to store the no of ways to get to a bad shift in i moves
code: vector < long long > dp1 ( k + 1 ) , dp2 ( k + 1 ) ; if ( s == t ) { dp1 [ 0 ] = 1 ; dp2 [ 0 ] = 0 ; } else { dp1 [ 0 ] = 0 ; dp2 [ 0 ] = 1 ; }