1
$\begingroup$

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

$\endgroup$
1
$\begingroup$
  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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.