dp2 [ i ] to store the no of ways to get to a bad shift in i moves
dp1 = [ 0 ] * ( k + 1 ) NEW_LINE dp2 = [ 0 ] * ( k + 1 ) NEW_LINE if ( s == t ) : NEW_LINE INDENT dp1 [ 0 ] = 1 NEW_LINE dp2 [ 0 ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT dp1 [ 0 ] = 0 NEW_LINE dp2 [ 0 ] = 1 NEW_LINE DEDENT