scratch
§ DP as Path Independence
created 2021-06-27 · last edited 2022-05-30
- 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).
❦