### __Noice__'s blog

By __Noice__, history, 10 months ago,

For other topics, It is easy to visualize and learn the algorithms but i am not able to grasp how to solve questions with dynamic programming. I have tried solving problems but it doesn't seem to help as i am not able to get to answer without the help of editorial. Any help would be appreciated, I want help so that atleast i am able to answer decent amount of questions till 2000 level on codeforces on dp.

• -5

 » 10 months ago, # |   0 I am not an expert at DP, but have you tried the CSES problemset? I think DP is extremely general. Basically any time you have a problem that can be solved optimally when you have optimal solutions some subproblems, and these subproblems are of the same type as your original problem, you can use DP. It is more of a mindset than a technique. However, there are some standard DP problems, which are covered by the CSES problemset, and I think if you solve those, it will be much easier to think in a DP-way and to spot when DP is useful.
•  » » 10 months ago, # ^ |   0 Thank you for replying Hmys. Can you tell me how should i go about solving CSES prolem set? Like I have tried one or two problems but each time when i try to solve them again, i forget how i solved it earlier.
 » 10 months ago, # |   0 This CF blog lists some resources you might be interested. Among those, I'd recommend Errichto's tutorial most. His LeetCode video is nice as well if you are looking for some practice.
•  » » 10 months ago, # ^ |   0 Thanks a lot zhang1pr . I will try looking at tutorials and then solving the problems.
 » 10 months ago, # |   0 https://www.youtube.com/playlist?list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY this playlist covers all models of dp .
•  » » 10 months ago, # ^ |   0 Sure i will check it out
 » 10 months ago, # |   0 Nearly all DP tasks below 2000 are solvable using DFS + memo. I find this much easier to understand than finding state transitions. The way I intuit DFS + memo is that I realize that there are a limited amount of states for the program to be in, thus if we searched all of them we can avoid doing repeated work if we use memoization. I used this technique to solve the recent problem C: The only parameters we care about during DFS are the position of the array we are in and whether or not we swapped x and y the call before. So the memoization array is a 2-D array of size[2000002][2]. Now we just need to fill the entire memoization array and return memo[0][0]. My submission: 191447995
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 I always use python's cache to solve dp, but it always RE or TLE.maybe this is not a good way.
 » 10 months ago, # |   0 Practice more questions and accumulate routine If you practice more questions, the definition of dp of some questions will be seen at a glance; But it is a few questions after all. Analyze the nature of the topic, understand what information you need, and then use the information you need to establish the dp equation. Pay attention to the information transmission process A dp definition should be changed; Or find out if this dp has monotonicity of decision, and see if it can use quadrilateral inequality (slope optimization should also work); Or optimize this dp with data structure; Or see if there is redundant information in the dp that can crush the dimension ——Transfer from c2023cyjMy English is not very good, please forgive me.
•  » » 10 months ago, # ^ |   0 6
 » 10 months ago, # |   +35 Saucin', saucin', I'm saucin' on youI'm swaggin', I'm swaggin', I'm swaggin', oh-ooh (swaggin')I'm ballin', I'm ballin', Iverson on you (swish, ooh, ayy)Watch out, watch out, watch out, yeahThat's my shot, that's my shot, that's my shot, yeahSpendin', I'm spendin' all my fuckin' payI got me some braids and I got me some hoesStarted rockin' the sleeve, I can't ball with no JoesYou know how I do it, Concords on my toes(This shit is hard) oohI ain't rich yet, but you know I ain't broke, ISo, if I see it, I like it, buy that from the store, I (store, I)I'm with some white girls and they lovin' the coca (coca)Like they OTDouble OT like I'm KD, smokin' OG (smokin' OG)And you know me, in my 2-3s and my gold teeth (and my gold teeth)Bitch, I'm smiling, bet you see me from the nosebleeds (nosebleeds)I'm the new three and I change out to my new 3s (to my new 3s)White IversonWhen I started ballin', I was youngYou gon' think about me when I'm goneI need that money like the ring I never won, I wonSaucin', saucin', I'm saucin' on youI'm swaggin', I'm swaggin', I'm swaggin', oh-oohI'm ballin', I'm ballin', Iverson on youWatch out, watch out, watch out, yeahThat's my shot, that's my shot, that's my shot, yeahSpendin', I'm spendin' all my fuckin' payOoh, StoneyCigarettes and a headbandCommas, commas in my head, manSlumped over like a dead manRed and black, 'bout my bread, manI'm the answer, never questionLace up, learn a lessonBitch, I'm saucin' (wow), I do this often, don't do no talkin' (no)My options right when I walk in, jump all them Jordans (ooh)I'm ballin', money jumpin'Like I'm Davis from New OrleansOr bitch, I'm Harden, I don't miss nothin'Fuck practice, this shit just happens, know y'all can't stand it (ayy)I have it, I never pass it, I work my magicHigh average, ball on these bastards, it makes me happyIt's tragic, I make it happen, and all y'all Shaqtin'White IversonWhen I started ballin', I was youngYou gon' think about me when I'm goneI need that money like the ring I never won, I wonSaucin', saucin', I'm saucin' on youI'm swaggin', I'm swaggin', I'm swaggin', oh-oohI'm ballin', I'm ballin', Iverson on youWatch out, watch out, watch out, yeahThat's my shot, that's my shot, that's my shot, yeahSpendin', I'm spendin' all my fuckin' payOoh-oohOoh-oohOoh-oohOoh-ooh