Dynamic Programming
When should we think about using dynamic programming?
Satisfied both two following situation.
1. When if following one of condition is true
- Find maximum value or minimum value.
- Existed or not, by
booleanvalue. - Count all possible solution (return just count).
2. Cannot rely on sort or swap operation.
3. Avoid greedy algorithm
What's the steps when using dynamic programming?
Status (State)
How to represent memory by data structure?
Function
How to pass through the memorial data structure?
Initialization
How to start the memorizing procedure and think about the boundary conditions?
Answer
Where is answer? Is it the last element in memorial data? Or it need to record any maximum or minimum value?
Routines
Matrix DP (2-D memorized)
Status: f[i][j] means to get the value by the start point to the position [i][j]
Function: different step approaches need to consider carefully
Initialization: in most case it doesn't needed
Answer: f[last_i][last_j] or recording max value or min value (depend on question)
Example: Triangle, Unique Path, Maximal Square...
Sequence DP (1-D memorized)
Status: f[i] means first 'i' position/number/alphabet
Function: f[i] = f[j] ... j is the position before i
Initialization: f[0] should be initialized with a certain value
Answer: f[length-1] or f[length]
Example: Partition Palindrome, Word Break, Longest Increasing Subsequence...
Two Sequence (2-D memorized)
Most of time, we setup 2-D memorized array has one plus original length, e.g. memo[len+1][len+1]. Why? Because we have to calculate the case of zero, and this also lead to the index of what we got should minus one, e.g. s.charAt(i-1).
Status: f[i][j] means the first [i] number/alphabet and first [j] number/alphabet
Function: f[i][j] is the relationship of ith in first sequence and jth in second sequence
Initialization: consider about f[i][0] and f[0][j]
Example: Longest Common Substring, Longest Common Sequence, Edit Distance, Palindrome Boolean Matrix...
Backpack (Difficult Part)
Typical Question: Given N integers, one target, output if several number can be combined to get the sum as the target.