Bottom up DP vs top down DP (which one to use?)


  • 0
    A

    I wrote both bottom-up dp and top-down dp. I timed both methods on my laptop, where their speed is comparable.

    However, my top-down dp solution is not acceptable on leetcode (time exceeds), while the bottom-up is okay (beat 70%).

    What makes the difference?

    Thank you


  • 0

    Probably you forgot to memorize the result already calculated which would become a brute force version.


  • 0
    A

    @clydexu
    Thanks for the reply. Both codes cost comparable time on my local environment. So I wonder why top-down doesn't work on leetcode. Do you think it is because of the overhead of recursions on leetcode python environment?


  • 0

    @Ashi I am not familiar with python environment. Just from my experience on C++, recursion costs really tiny overload that I even hard to believe. And top down usually takes less time due to access to limited slots.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.