# Dynamic Programming -- source

Back to Computer-Science-Concepts
- in directed acyclic graphs can be
*linearized*: ordered in an array
- if we want to minimize distance in a weighted graph, and both A and B point to C, then
`dist(C) = min{dist(A) + AC, dist(B) + BC}`

- solving a collection of subproblems,
`{dist(u) : u in V}`

from left to right
- dynamic programming is breaking a problem into solving subproblems, and using previous subproblems to solve later subproblems
- longest increasing subsequence problem (not necessarily consecutive) can be solved using DP
- construct a graph, with directed edges between each node whenever possible, forming a dag
- now find longest path in dag, and track previous node and backtrack for the actual subsequence

- edit distance: the cost of the best possible alignment between two strings
- minimum edits (insertion, deletion, replacement)
- our subproblem will be finding the edit distance between a prefix of s1 and s2

## Subset sum problem

- NP complete problem; is there a subset whose sum is 0?