zeddie's blog

Want to get good in DP
By zeddie, history, 5 years ago, In English

I have been trying to learn Dynamic Programming for 2 months now, I completed a couple of youtube playlist, solved practice questions for beginners on Atcoder and some super easy questions on Codeforces.

Now, whenever I try questions from a range 1600+ questions, I am not able to do it. Also most of the time Editorial also does no good to me. I am on the verge of collapsing, it feels like Dp is not meant for me.

All those programmers who believe that they have a good grip in Dynamic Programming, Please show some support to me, share some resources to me and guide me a little.

Thanks in advance.

With Regards, Anubhav Singhal

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

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The tutorials are some of the best resources you can get. If you do not understand a significant number of them then the problems where to complex and you should solve simpler ones.

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

in my opinion stop DP for some time... go for other topics, return to DP after a few weeks you will see the process of thinking changes when we take a break from something which in turn will help you a lot

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

    Pretty much agree. To be able to solve DP after the person learned it, the person needs to think right. The person needs to know how to make transitions and to use the minimum amount of states he/she can use while solving the problem to pass without timelimit. I'd say, greedy and maths helps in that. People would say how? Greedy/maths is very different from DP. But in fact, greedy and maths would help the person to think in a better way to utilize the usage of the minimum possible states. But, if the person doesn't understand how DP works, then he should learn it first.

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

    From the last 6-8 months, I have been solving questions of various topics from problem sets. And, I believe I have established a good grip on fundamental topics. Currently, topics like Graph and DP are the only obstacles.

    So, my question is, If I am supposed to take a break from DP, then what are you recommending me to solve?

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

      solve greedy and constructive also dfs,bfs and other tags which takes a good grasp on recursion... from my personal experience return to dp after you are able to solve atleast 1700 rated dfs and 1500+ other tags like bitmasking,binary etc. you will see dramatic improvement in the way you approach a question .

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

        Okay, lemme give some time to 1700 rated dfs questions, either way, I will learn something.

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

    The same worked for me. I am not that good at dp but I have got the idea how to solve the dp problems.

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

My advice you to not learn more dp examples at a time that is where many people confuse for one over other and make mistakes. Start learning basic dp concepts and start solving problems immediately you will face a lot grid, string problems then when you search for regarding topic you will learn fastly. Don't learn more dp examples at start itself.

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

    What is the purpose of arr[0]=0; in your code?

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

    That's exactly what I did, First I read a few articles about basic concepts of DP. Then I tried examples.

    Still, What dp concepts are you suggesting, I might have missed few of those.

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

I just saw this blog

Maybe it'll help you

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

I think you should try to solve some classical problems on paper for some examples. Then just do their variations(for that cses dp section is best). Then learn about different types of Dp with help of Codeforces blog and solve the atcoder dp contest.

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

I don't know if it's the same with you but I felt the same way until I found code for this problem that used recursion instead of iterating. It's more intuitive to do dp recursively so I think you should try that if you haven't already.

→ Reply