DP as a DAG
Can represent dynamic programming algorithms/situations as a DAG (e.g. state 1 leads to state n but also state 3 leads to state n).
Subproblems
Approach DP by figuring out what the cases are for every subproblem. e.g. choosing between n options each iteration (n choices)
Edit Distance
Getting a string x to look like string y in minimum edit distance Possible operations
- Substitute char from x to char from y
- Delete char from x
- Insert char from y