I am new to DP problems, and I just can’t see why we are using DP in CHEFBR. I mean, doesn’t it look more like a Permutation and Combination question? Can someone please tell how they identified it to be a DP
1 Like
Permutation and combination isn’t mutually exclusive with dp. In fact, both of them go well along each other very often.
1 Like
Ah, but can you please share why this looked like a DP problem to you?
You had to find the number of subsequences which which had balanced parenthesis.
Normally there are 2^N such subsequences, with n <= 100 it is impossible with brute fore
One thing to note about subsequence problem is that a subsequence from index 1 to k , where k < n, will be part of a sequence from 1 to n. i.e. It can be divided into sub problems which pretty much is the reason we use dp.
Another example of dp for sequence is LCS problem.
Hope this helps
1 Like
It occurred as dp to me because I could use the previously computed result for a range to compute a new result. However I used a combined dp + recursive approach (which is not really a good idea). To give a vague idea of what i used-
solve(left,right){
…
for each pair i,j
dp[i,j] = dp[i-1]*solve(i+1,j-1)
…
}
Idea = To form a subset having i,j bracket,we can choose either one of the subsets to its left or one of the subsets completely in the center or both.
This wasnt very efficient and there are more efficient ways but this was very intuitive and passed with a couple of optimizations.
Think this manner: For DP to be applicable we need two things, Optimal substructure and overlapping subproblems. If we talk about optimal substructure, then finding the number of valid brackets in a range say (i,j), we need to find the summation and all permutations(with this i,j) of all valid brackets of the ranges that lie within (i,j). Thus, we can obtain Optimal solution for(i,j) by using optimal solutions to all the subranges. If we talk about overlapping property, lets say, a closing bracket of ith value occurs at some index k<j. We need optimal solution of (k,j) for our calculation. This subproblem may be required for some other (i',j') calculation when a[i']=a[i] and i'<j. Hence, the two conditions satisy and we can now apply DP.
Yes, it looks like PnC problem but we still need to see whether we can actually use it. I tried that also, but couldn’t get 100 points during the contest. Here is my solution based on the DP explained in editorial. Even I was applying DP wrong way during the contest but got the mistake now.
Hope it clears!! 
3 Likes
Ah. Thanks!
Thank you!
Thank you!