Sep 2010
1 / 3
Sep 2010
Sep 2010
cainjonm
Sep '10

When it comes to dynamic programming, is there any cases where the top-down approach is simply infeasible? (or far less efficient? If so, why?) I mean, when is there a reason to 'convert' the top-down approach into a bottom up approach? I recently watched an MIT lecture on dynamic programming which used the LCS as an example, it ended with the person changing the top-down code into bottom-up, but what i didn't really understand was why? Is it just because he wanted to teach how to do it bottom-up, or is there a performance increase?

P.s. I hope my questions don't sound too 'rude', I'm genuinely interested in an answer to this.

Thanks.

  • created

    Sep '10

  • last reply

    Sep '10
  • 2

    replies

  • 561

    views

  • 2

    users

leppyr64
Sep '10

Two main reasons, one main cause, recursion.

With the top-down solution you typically have the overhead of calling a function, declaring the variables and such. This will increase your time.

Also, If your state space is very large, you will encounter stack overflow If you go too many levels deep into the recursion.

Suggested Topics

Want to read more? Browse other topics in Off-topic or view latest topics.