No one has replied
the approach of top_down is great
could you tell me why top - down solution is o(n^2) time complexity ?
my understanding is worst case would be linked list
then f(n) = o(n) + f(n-1) = o(n^2).
Line 6: RuntimeError: maximum recursion depth exceeded while calling a Python object
In solution 4 (bottom-up, O(n) space), the last row of triangle will still be modified. We can avoid this with a little modification:
It's because the last method memorizes the results of the subproblems via a dict when it first encounters, and thus duplicate subproblems are not recomputed. Therefore it outperforms the first method.
That bottom-up approach is very clever. Thank you for sharing that.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.