sidO_O's blog

How to improve DP problem solving skill?
By sidO_O, history, 3 years ago, In English

Yeah,the common answer would be "PRACTICE". I face some problems practicing DP problems.I barely can upsolve <= 1800 rated DP problems. I can identify DP problems but cannot really make way to solve it in contest time. The most common problem I face is to "FINDING THE STATES". Moreover,I feel very uncomfortable with iterative DP approach. As maximum DP solutions are solved in iterative way,it becomes very hard for me to get them. I'm seeking some suggestions to be a good DP problem solver.

Sorry for my poor English :(

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

For Hindi Audience, I found these as very good Dp Resources.

Aditya Verma
Kartik Arora
Key Point
→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I first learned DP here: https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns

If you are uncomfortable with iterative DP, maybe try recursive DP first, if you are more comfortable with that. Then, as you get better you can switch to iterative DP... just a suggestion.

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You are wrong with that iterative thing. In my experience you rarely need to do iterative dp.

Btw I learned a lot from this video when I was learning dp.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I started out with iterative dp. It was some 2D DP task but after seeing recursive dp i think it's more easier than the iterative one. But I've seen a lot of people preferring iterative version. Is there any benefits to it or am i wrong with the difficulty comparison?

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The video is unavailable, can you name the channel, please?

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      That content is no longer free.

      "When you are good at something, never do it for free."

      That channel owner was bought by some startup for providing dsa course as far as I know. That video was editorial for this problem.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

I recommend CSES DP problemset, and this gym made by galen_colin.

The gym has also a video explaining solutions.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are not allowed to view the contest

    I think the gym link u provided is private, i get this when i try to enter it

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

On low skill levels, I recommend to think in terms of forward DP. It is much easier, having a current state, to see what states could be the next. Just like in BFS (DP is BFS).

In some problems forward DP doesn't work, but it's rare.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Sometimes push-dp (what you said) is nicer, other times pull-dp is nicer, although usually both work.

    I usually just implement whichever seems easier to me, so I think it's best to just practice both.

    → Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Start with recursive dp. Do a lot of problems with it. Then move to iterative dp, because it's nicer to code, and is usually faster.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You are not alone bro, the first time I came to a DP problem and went to tutorial or solutions, I see the majority of solutions implemented DP in iterative method. But for a novice like me I feel it's so uncomfortable and unnatural, though i still understand the solution. From that point, i started solving more and more DP problems and got used to it in recursive way for a while. Later on, after solving and reading other solutions i feel both ways have their own advantages and feel comfortable with either ways. So if you're just like me, keep solving DP in the way you feel comfortable and maybe you will discover the other way through your journey. Don't panic.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Personally i think "what is the information would i need to contruct a bigger solution" and go from there.

Lets say i want to make a value x using k numbers from a set of n numbers. If i had all the possible values using numbers from 1 to n-1 using at most k-1, i could just try to add the last number to all of those and get the full answer, therefore a dp[x][n][k].

A lot of times it won't be as straightforward but it really is just practice (as much as i hate to say it). I had similar problems not too long ago and by solving problems and learning the ideas i couldnt get i became a lot more confortable with it

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

I just had a question regarding dp

Can we use memoisation dp and iterative dp as per our comfort or memoisation may result in Memory limit exceeded

I have done dp with memo in many questions(it works fine perfectly) but i am told by my friends to not use memo dp

→ Reply