Three dynamic programming techniques

Question

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?

EDIT: I found them in this link

Answer 1

1. Binary choice - it refers to the fact that for each job you have two choices: to do it or not.
2. Multiway choice - similar to the above, in the considered problem, at each step you had a range of choices.
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$