murderousbread's blog

By murderousbread, history, 5 years ago, In English

I have been trying for almost a month now to try and understand DP. I started of with first ensuring that I understand recursion correctly. For this I practiced Recursive segment tree problems, And a few basic recursion problems. In addition, I even switched to recursive binary search, which I honestly dislike, just to ensure that I am not lacking in my understanding of recursion.

Next, I started reading tutorials that introduced DP. Ones like this one, https://www.topcoder.com/community/competitive-programming/tutorials/dynamic-programming-from-novice-to-advanced/ , https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/tutorial/ , and a few others.

The problem: While I am able to understand the approach taken in the problems that I have seen, I am unable to apply it myself. To put it differently, I understand the solutions, but am unable to come up with such solutions on my own. And, some of the harder DP problems I am unable to understand even when I read the tutorial multiple times. Its only when I read the code, the tutorial, trace a few test cases that I just start to understand how the program works, leaving me very far away from being able to code it on my own, much less think of it.

My request: How do I improve upon this? I do try various problems on CF and CC, and unfortunately still am unable to get DP. Is the solution even more practice? Obviously there is no single problem that will cause the idea of DP to just, click in my brain. I wish to know if anyone else has faced a similar issue, and if yes, how did they get past it? I am not averse to hard work, just would like to know if only practice will not help me get better.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Again and again, just practice. Seriously, if you cannot understand a problem, just try easier problems and, gradually, more difficult ones. To be honest, there's nothing anyone here can/will do for you to make your brain understand DP better.

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

    -> I am not averse to hard work, just would like to know if only practice will not help me get better. Its not that I don't want to work hard, I just do not want to end up at a dead end after a lot of hard work.

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

      I just do not want to end up at a dead end after a lot of hard work.

      How do you know that you would end up at a dead end?

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

        Thats the whole point of this post. Is the method of only practicing DP problems to try and understand DP a dead end? If yes, then what else should I supplement my practice with.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 3   Vote: I like it +22 Vote: I do not like it

          No, it's not a dead end. It may seem like it sometimes, but really, practicing solving gradually harder problems and reading solutions/other people's code is how you get better at any type of problem.

          I'd recommend the Atcoder Educational DP round. I think that definitely increases gradually in difficulty.

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

dp is just brute force where you reuse previously solved subproblems

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

Understand proof of solutions. It will help.

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

DP = Double Penetration

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

I did this problem 1032C - Игра на фортепиано and read a solution for it (link). After this I realized that dynamic programming was recursion, so then I read how to convert recursion to dp here (link). Then I tried it on some simple DP problems.