## ยง DP as path independence

- Dp is about forgetting the past / path independence. Doesn't matter how we got to a state, only what the state is. For example, to DP on subsequences, we don't care about how we got to a given subsequence. We only care about the final result that we computed for that subsequence. This lets us "extend" knowledge about a subsequence. So we go from
`2^n`

(subsets), to `2`

followed by `2`

followed by `2`

followed by `2`

, since at each stage, we forget how we got there and collate information.

- In this light, the recursive sub-computation is the "path dependent" part since it tries a path. The path independence states that it's safe to cache the results of the sub-computation, since all that matters is the final state (inputs).