# Three dynamic programming techniques

I've noticed three terms that come up when I look at dynamic programming exercises.

1. Binary choice - seen it in a weighted interval scheduling problem.
2. Multiway choice - seen in a segmented least squares problem.
3. Adding a new variable - seen in a knapsack problem.

What do all these mean with respect to dynamic programming?

3. Adding a new variable - when the space over which you do the dynamic programming is not expressive enough, you have to enhance it, for example by adding a new dimension. Imagine you have the $\mathbb{R}^2$ plane and refer to the points by their $x$ and $y$ coordinates, then informally speaking you could "add a new variable $z$" to make it into the $\mathbb{R}^3$ space.
I hope this helps $\ddot\smile$