THERE_IS_NO_RETURN's blog

i need help in dp
By THERE_IS_NO_RETURN, history, 3 years ago, In English

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.

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

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

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.

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

    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?

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

      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.

      → Reply