Approach for the question Cards

I always get stuck at this point where dp states depend on both forward and some backward state.In this question :

I came up with this recurrence relation:

dp[r][g][b] denotes if its is possible to reach this state containing r ‘R’,g ‘G’,b ‘B’.

and relation is dp[r][g][b]=dp[r][g][b] or dp[r+1][g][b] or dp[r][g+1][b] or dp[r][g][b+1] or dp[r-1][g+1][b+1] or dp[r+1][g-1][b+1] or dp[r+1][g+1][b-1].

I want to solve this iteratively without recursion,however i dont know how to iterate,and what to calculate first.

Plz any help is appreciated.

1 Like

As you surely know, the objective is to make sure all the states which a state s depends on are calculated before s. In this particular problem you can see that after every state the number of cards decreases by one. So f(r, g, b) will depend on some states f(r', b', g') as you mentioned above, but observe that r + g + b = r' + g' + b' - 1. And that’s it… just fill up the states in decreasing order of r + g + b.

for(sum=start_value; sum>0; sum--)
    for(int r=0; r<=sum; r++)
        for(int g=0; g<=sum-r; g++) {
            int b = sum-r-g;
            // calculate dp[r][g][b]
1 Like

Thanx a ton!!

Could u plz tell from where should i practice dp. I am currently doing dp problems from codeforces.


1 Like