__Noice__'s blog

How to get started with dp problems?

By __Noice__, history, 22 months ago, In English

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.

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.youtube.com/playlist?list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY this playlist covers all models of dp .

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I always use python's cache to solve dp, but it always RE or TLE.maybe this is not a good way.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. Practice more questions and accumulate routine
  2. 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
  3. 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 c2023cyj

My English is not very good, please forgive me.

→ Reply
»
22 months ago, # |
  Vote: I like it +35 Vote: I do not like it

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

→ Reply