How I will know in this problem Multi-dimensional dp is used ?
1 Like
If one state could not able to solve your problem then you must increase your state. One dimension is possible when you have only looking for straight-forward solution.
There is already plenty of material available at quora or other sites. Have a look on these one.
See this tutorial that will assure help you u differentiate both single dimension and multi-dimension
It is actually a good question. But sadly, the only answer I can give right now is practice. Practice more and more. Check out the algorithms given at geekforgeeks for basics. The thing is, while we can easily say what kind of table/array we need for Q based of standard algorithms (Eg- Longest alternating subsequence, a Q based on algorithm of Longest Increasing Sub-Sequence needs only a 1-D array and ahs similar approach).
My thumb rule so far has been, if there are multiple possibilities for a sub-problem, its mostly a 2-D array approach. (Eg- In Fibonacci number problem, there is only one possible value of fib[I], so 1-D array. But in finding longest common subsequence, there are 2 possibilities of “the characters match, or they do not match.” So 2-D array. But its just a “rule-of-thumb” and not necessarily correct in all situations)
Try to develop the “killer instinct” by practice, because that’s what will help you tackle the non-standard dp problems. Its just like solving Maths to me…once you develop the killer instinct and logical mind, you will find it getting easier to think of the solution.
What I suggest is, build up some basics, check out some algos (try to make your own approach first). The first step is doing the standard algo, solving Q based on them, and then attempting past contest dp problems (Don’t read editorial before attempting!! Read editorial only if absolutely necessary. Contest problems are will prove to be most efficient towards building up your killer instinct. But a good grip on base is needed before attempting them.)
2 Likes
Actually, there isn’t anything like “multi-dimensional” DP. I think those are just states of DP. As you know, in DP we need to store the value so that we can use them for future reference and hence, we save our time by calculating the same operations again and again.
So, we need to maintain a table, call it
DP table.
To maintain any table, we need to have some coordinates. Like for row i and column j value is dp[i][j]. Next time when we need to solve for dp[i][j] we will directly fetch the solution from there, saving lots of time.
Now, here i and j are called stated of dp. It solely depends on the problem the how many states you need to have to compute any DP table.
During optimization of DP, we do bitmasking by second coordinate of dp table.
And of course, you need to get the grasp of the problem like it should click in your mind, once you need to recognize that this is a DP problem then after second thing should be that… ok, so now I need to store the values a DP table… How many states are needed?
Finally, first I was also confused by dimensions of DP. But luckily, there aren’t any. They are just states that you need to calculate DP table.
This is my first answer hope this helps. Peace.
I was facing the same problem when I started with DP. One of my friend gave me a suggestion about how to approach DP problems. He told me to prefer the memoisation or the top-down approach for such problems. This approach requires a recursive function to be written. Now, while writing a recursive solution to the problem, you will get to know intuitively about the changing parameters and hence can easily form a dp table through it by memoisation.
1 Like