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.
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.
https://www.youtube.com/playlist?list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY this playlist covers all models of dp .
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
I always use python's cache to solve dp, but it always RE or TLE.maybe this is not a good way.
——Transfer from c2023cyj
My English is not very good, please forgive me.
6
Saucin', saucin', I'm saucin' on you
I'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, yeah
That's my shot, that's my shot, that's my shot, yeah
Spendin', I'm spendin' all my fuckin' pay
I got me some braids and I got me some hoes
Started rockin' the sleeve, I can't ball with no Joes
You know how I do it, Concords on my toes
(This shit is hard) ooh
I ain't rich yet, but you know I ain't broke, I
So, 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 OT
Double 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 Iverson
When I started ballin', I was young
You gon' think about me when I'm gone
I need that money like the ring I never won, I won
Saucin', saucin', I'm saucin' on you
I'm swaggin', I'm swaggin', I'm swaggin', oh-ooh
I'm ballin', I'm ballin', Iverson on you
Watch out, watch out, watch out, yeah
That's my shot, that's my shot, that's my shot, yeah
Spendin', I'm spendin' all my fuckin' pay
Ooh, Stoney
Cigarettes and a headband
Commas, commas in my head, man
Slumped over like a dead man
Red and black, 'bout my bread, man
I'm the answer, never question
Lace up, learn a lesson
Bitch, 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 Orleans
Or 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 magic
High average, ball on these bastards, it makes me happy
It's tragic, I make it happen, and all y'all Shaqtin'
White Iverson
When I started ballin', I was young
You gon' think about me when I'm gone
I need that money like the ring I never won, I won
Saucin', saucin', I'm saucin' on you
I'm swaggin', I'm swaggin', I'm swaggin', oh-ooh
I'm ballin', I'm ballin', Iverson on you
Watch out, watch out, watch out, yeah
That's my shot, that's my shot, that's my shot, yeah
Spendin', I'm spendin' all my fuckin' pay
Ooh-ooh
Ooh-ooh
Ooh-ooh
Ooh-ooh