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

Автор __prudhvi___raj___, история, 4 года назад, По-английски

what is the procedure for converting top down dp to bottom up dp?

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

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

I am not really fit to give advice as of now but I started out with top down and lately I have been solving few dp questions on bottom up manner too.

Personally I like to think in this manner.

How can I come from the previous index to the current index. (When I am trying to solve in an iterative fashion)

With that thought I try to look for the recurrence relation and how many states would it include. (remaining are the initial conditions like dp[0], dp[1] etc)

For top down. It's necessary to start with the recurrence itself and see for the recursion tree. Followed by the number of states and if memoization is possible.

And I personally feel one shouldn't think of how to convert it since its not really required. So rather pick up whatever you are comfortable with. (dp with less states usually are better to be done in iterative manner, dp problems which may require more states probably >2 are better done in top down manner)

Anyways I have a fundamental problem of not being able to recognize a dp problem (mostly) during the contests so I don't even get the chance to work them out. (That is a huge difference since knowing whether you can apply dp to the problem or not makes all the difference.)

P.S- If you really want to convert top down to bottom up. Its not very different. The recurrence remains the same. You just need to see how you can convert your recursion into loops once you solve it with top down.