learn dynamic programming

so i saw 3d DP being used in problems in this month’s long challenge , i will request the coders who already have a hold of 3D DP to help out , on how to START? video tutorials? and practice problems , because i tried going through the editorials , but it was kind of tough for me to understand those without having a prior hold of it , so help required :slight_smile:
video links of 3D DP will be much appreciated

You can try these problems. These problems use 3D DP.

687C. The Values You Can Make

711C. Coloring Trees

3-D dp is nothing special, and you wont see many (or rather any) tutorials on it. If you have a good hold on dp, then irrespective of dimensions you can solve it. If however, you are facing problem in a particular Q, it means you are not used to that kind of dp in general instead of a problem with dimensions.

But of course, there are some Q i found for 3-D dp-

https://discuss.codechef.com/questions/85551/3d-dp-question

Also, there is a 3-D knapsnack problem, cant get the link atm but heard its a standard one if you want to give it a try.

EDIT: Didnt saw sudip already gave the questions.

Well,as you said that you need to learn it, actually you dont need that. The thing which guided most of the coders who solved this question is the intuition they built up by practicing dp problems. Even i got the intuition, but did a silly error in table-filling , getting a bad,bad WA. XD

Just keep practicing, thats all we can say. 3-D dp is nothing special, whats extra in this is that you need more visualisation and thinking on states and their relation.

2 Likes

3d DP is not a different thing than 1d DP or 2d DP, if you understand the main concept of dynamic programming. Actually, I solved the problem with 4d DP, in this long contest. The number of factors you need to maintain for the recursive functions are the demensions of DP, nothing else changes.

1 Like

Below is a good 3D dp sum for beginners. A div2 C problem on codeforces.
You can have a look at the editorial for this problem to understand why 3D dp is used here.
http://codeforces.com/contest/835/problem/C

1 Like

bro i cannot try without learning :slight_smile: that is the reason i asked for learning links

ohk i got it

oh i got it

Exactly my point!

4-D dp tho, sudip stud XD :smiley:

i jast saw your submissions for this month’s long , which question did you solve by 4d btw :stuck_out_tongue:

I added an extra dimension! :stuck_out_tongue:

https://www.codechef.com/viewsolution/15010538