Dynamic Programming
Concept
Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again.
Dynamic programming can be seem as an optimization of recursion.
Using bottom-up solution which means prior results will be used to optimize the solution. We get the bottom results first, and built up others by bottom results.
Don't have risk of stack overflow because of bottom-up. (Memoization using top-down would have it)
[Medium] No.279 Perfect Squares
Approach: Dynamic Programming
Time Complexity: check the link.
Space Complexity: O(N), where N is the size of dp array.
![](images/279_dp.png)
(The above image is from leetcode.)
[Hard] No.42 Trapping Rain Water
Approach: Dynamic Programming
Time Complexity: O(N), where N is the number of the list.
Space Complexity: O(N), where N is the size of dp array.