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.

(The above image is from leetcode.)

class Solution { public: int numSquares(int n) { //data base vector<int> vec; for(int j = 1 ; j*j <= n ; j++) { vec.push_back(j*j); } vector<int> dp(n+1,INT_MAX-1); dp[0] = 0; for(int i = 1 ; i <= n ; i++) { for(int k = 0 ; k < vec.size() ; k++) { if(i >= vec[k]) { dp[i] = min(dp[i], dp[i-vec[k]] + 1); } } } return dp[n]; } };

[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.

class Solution { public: int trap(vector<int>& height) { if(height.empty()) return 0; int n = height.size(); vector<int> leftMax(n,0); vector<int> rightMax(n,0); int ans = 0; leftMax[0] = height[0]; //left max for(int i = 1 ; i < n ; i++){ leftMax[i] = max(height[i], leftMax[i-1]); } rightMax[n-1] = height[n-1]; //right max for(int j = n - 2; j >= 0 ; j--){ rightMax[j] = max(height[j], rightMax[j+1]); } //calcualte difference for(int k = 0 ; k < n ; k ++){ ans += min(leftMax[k], rightMax[k]) - height[k]; } return ans; } };