Hi Friends! Here is the problem created by one of the user's at my site. I don't ask for solution (at least yet, ha-ha, going to try thinking a bit more) — but invite you to check your skills, presumably, at DP.
It has somewhat lengthy description, but boils down to counting number of differing subsequences in 01
-string with required balance of zeroes and ones. I quickly started scratching typical DP-like double loop, but soon found it doesn't account for possible duplicates: i.e. in the sequence 1010
we can pick 10
subsequence in two ways but they are not considered different. Results seemingly can grow somewhere to 10^18
so naively keeping all sequences in hashtable doesn't look like a viable approach. Sorry for my naive thoughts, I'm obviously lame at this and perhaps there is a known solution. However if you, like me, don't know it, you can spend some time on it...
Here is almost the same task, the only difference is that subsequence must be a right brace sequence.
Thanks! That sounds like a generous hint — about the relation to brace sequence problems (though to my weak brain it is yet to figure out if this is the same, given that 0-1 sequence doesn't actually need to be as "right" as brace sequence)