[Math] Three dynamic programming techniques

algorithmsdynamic programming

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

Best Answer

  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$

Related Question