2.13 1-D Dynamic Programming

Dynamic Programming

Dynamic programming involves breaking down the problem into smaller subproblems and storing the results of these subproblems to avoid redundant calculations.

It is similar to recursion, except that redundant (repetitive) calculations are avoided by storing the answer to subproblems.

what’s the recursive rule.

Dynamic programming is similar to deep learning in the sense that you get extremely complex and intelligent behaviour for free, by defining simple rules

Explain the iterative recursive build up of knowledge, bank on FACTS and abstract them 

Change function

• Top-Down Approach (Memoization): This is essentially recursion with memoization. In this approach, you start solving the problem by breaking it down. If you see that the problem has already been solved, you simply return the saved result. If it hasn’t been solved, you solve it and save the result.

• Bottom-Up Approach (Tabulation): This approach typically involves filling up an n-dimensional table based on the results of smaller subproblems. In contrast to the top-down approach, you start solving the problem from the simplest possible subproblem and gradually build up the solution to the problem in question.

  
  

---

Longest valid parenthesis §

LC-32 Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

---

Knapsack §

---

Sliding Window §

# e.g [5, 3, 6, 2, 7]
l = 0
max_profit = 0
 
for r in range(1, len(prices)):
	curr_profit = prices[r]-prices[l]
	if curr_profit < 0:
		l=r
	max_profit = max(curr_profit, max_profit)
	
return max_profit

• This is considered a sliding window problem and dynamic programming problem. They often go hand in hand.
• It is dynamic programming because at every new [0, i] window, you’re checking whether including this new price point would be better than the known maximum out of the [0, i-1] window.
  • You check this by leveraging the fact that you know l must be the smallest value so far, since at each step curr_profit can only go negative if a number at the i index is smaller than the number at the l index.