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

i need help in dp
Автор THERE_IS_NO_RETURN, история, 4 года назад, По-английски

If you are comfortable with dynamic programming, especially the bottom up approach, can you share what was your way of learning and practice, I know there are a lot of advices out there, however i think its good to have efficient answers instead of random answers, thanks in advance.

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

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

When I learned dp, I usually make a recursive solution, check that it works, and then convert it to an iterative version so i know how that would look too. I think most dp problems (that are given in contests) can be solved iteratively, but it's usually easier to get a recursive solution for some of the harder problems.

After a while, it becomes easier to code an iterative version based off of a recursive solution that you found (but didn't actually put into code yet), because the overall style of the solution might be similar to another problem you've done.

For example, I solved problem D today in a similar way to finding the longest palindromic substring in $$$O(N^2)$$$ time, except with slightly different transitions.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    may i ask, how did you learnt Recursion? I am trying but still can't make recursive equations for even some easy level problems. can you suggest something?

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Try starting by solving recursive math equations, like the fibonacci sequence or a simple linear function like $$$f(0) = -5, f(n) = f(n-1) + 3$$$

      But I have to say, recursion isn't the easiest thing to learn. So take your time and don't expect to be a god with dp and/or recursion within a week.

      → Ответить