Блог пользователя murderousbread

Автор murderousbread, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    -> 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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +22 Проголосовать: не нравится

          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 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

dp is just brute force where you reuse previously solved subproblems

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Understand proof of solutions. It will help.

»
5 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

DP = Double Penetration

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.