Course 4: Dynamic Programming

题目：

• Text justification
• Triangle

1. 全局变量：不能多线程？
2. 红黑树，AVL tree，知道是什么就行

如何想到用DP

1. Max, min：找路径最大最小值
2. Yes or no: 等否找到和为多少
3. Count：一共有多少种走法
4. Cannot swap/sort

面试常见

1. Matrix DP
   1. Minimum Path sum
   2. Unique Path
   3. Unique Path II
2. Sequence
   1. Climing stairs
   2. Jump game (Greedy and DP)
   3. Jump game 2
   4. Palindrome partition 2
   5. word break
   6. longest increasing subsequence
   7. maximum subarray
3. Two sequence DP
   1. Longest common subsequence
   2. Longest common substring
   3. Edit distance
   4. Distinct subsequence
   5. Interleaving string
4. Backpack
   1. Backpack （滚动数组 %2 nice！）
   2. Backpack 2
   3. k sum
   4. Minimum adjustment cost

Note： 一般subarray(substring)连续，subsequence可以不连续。