tri_e's blog

SUGGESTIONS NEEDED
By tri_e, history, 4 years ago, In English

do we need to solve DP problems separately or just keep solving the problems in mixed pool and eventually everything will fall at its place

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

Comments Comments (13)
| Write comment?
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

What is DP?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Is this a joke?

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

    i have asked politely that which approach is better to improve in Dynamic Programming faster.Why are you so rude?Now i can understand why after solving over 3000 problems and distributed over 160 pages on your codeforces account you are still candidate master cause you don't know what DP is.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      Interesting! A green attacking a purple on rating. Btw it's true that one can be purple without knowing what DP is, if one is good at maths and implementation.

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

    double penetration obviously.

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

    DP stands for "Do practice"

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

I usually solve random problems. The problem with searching for DP problems is that you know the solution involves DP. I also recommend participating in virtual contests.

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

I personally feel that you must solve 80 to 100 questions on dp to get the idea. At least that worked for me. You can solve the starting 100 problems of dp from a2oj. It is very helpful and also the atcoder dp contest(take help from the Errichto video)

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

If you consider weak at DP, then you may try solving a bunch of problems on it.As per my experience, whatever I have learnt till now, I can tell you after you are all clear with the basics of a topic and you are able to use it while thinking, it all boils down to problem solving skills. If you really want to try some DP problems then (my opinion) you can go to leetcode DP section. They have a nice collection which covers almost all basic DP variants.Then you can randomnly solve problems on Codeforces for enhancing problem solving skills. Hope it helps.

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

    For approaching a dp problem as a beginner, should we always think for a recursive solution first and then do it in iterative ?

    I dont know what people mean by that, but many people recommended me to try recursive solution first.

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

      Hey, I will tell you how I approach. As a beginner in DP,I always struggled, like how to approach . Is it always that I have to think of recursive solution or sometimes it is beneficial to think of bottom up. So, I observed that the main thing which was tough for me was coming up with a recurrence relation. It just felt like magic. It was tough to come up with but when i saw the editorial, it seemed it is obvious. So , then what I did was to just keep thinking why I was not able to come up with that recurrence, where i went wrong or got confused . When i started doing in these type of problems, then slowly I was able to think correctly. So when people say, DP comes with practice , I think this is the area where people get more and more experienced with solving problems. So basically what i have solved till now is around 200 dp problems from 1600 to 1800 ( almost all on codeforces) and around 135 on leetcode. So, approach should be think hard, like don't give up for at least 1 hour or 1.5 hour. It has happened to me that I got the idea to solve a problem after 1.5 hours of thinking. and then if you don't get the solution then read editorial. Its not just for getting AC. You should be clear on why you were not able to think , is it was some hard to see observation, or some new concept. It may also be possible that you were going correct but you deviated along the way. In that way you learn a lot on hoe to think correctly on a problem and I think this strategy works for all kind of problems.

      → Reply