Dynamic Programming 1

what to do when asking a DP question

1. base case
2. induction rule: DP[i] physical meaning

find global min/max

1. recusion: DFS -> permute all possible outcomes -> optimal
2. BFS - heap
3. Greedy - need proof
4. DP

Q0: largest sum of a subarray

{1, 2, 4, -1, -2, 10, 1} => {1, 2, 4, -1, -2, 10} with max sum of 14

Q1: maximal product: cutting rope

Given a rope, cut the rope so that the product of total length is max

---

Last update: January 9, 2021