5
$\begingroup$

The usual criteria used to decide if a problem can be solved using dynamic programming is (1) if it has optimal sub-problems and (2) if it has overlapping sub-problems. Does the word "optimal" mean that DP can only be used to solve optimization problems? Otherwise, it would make more sense to write (1) as "if it can be decomposed in sub-problems" (i.e. it is recursive). Obviously, this definition includes optimization problems with optimal sub-problems.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Here is an example of a decision problem amenable to dynamic programming: is the edit distance between $x,y$ at most $d$? $\endgroup$ Commented Dec 2, 2019 at 14:56
  • 2
    $\begingroup$ Problems involving counting something (e.g., the number of ways of building a $3\times n$ wall out of dominos) can often be solved with what I'd call dynamic programming. More discussion here: cs.stackexchange.com/questions/79664/… $\endgroup$ Commented Dec 3, 2019 at 0:49
  • $\begingroup$ I wonder if problems "count ways to do X" aren't always equivalent to "find quantity optimizing Y". I can't think of Y for say, Fibonacci numbers, but that's not the same as saying no one can. $\endgroup$ Commented Dec 6, 2019 at 16:40

1 Answer 1

Reset to default
8
$\begingroup$

Dynamic Programming can be used to solve a problem as long as the problem has a recursive substructure and the sub-structural problems are overlapping. So, as long as a problem has the two properties, DP can be used for solving it. Problems with these properties are definitely not restricted to only optimization problems. So, yes.

Here are some good examples of non-optimization problems which can be solved quickly using DP:

  1. Coin Change Problem

  2. Counting the number of increasing subsequences in a given sequence

  3. If you forget everything, calculating upto the first $n$ Fibonacci Numbers using its recurrence relation can be done using Dynamic Programming.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Great answer, welcome to the site! $\endgroup$ Commented Dec 6, 2019 at 18:12
  • $\begingroup$ Thanks for the appreciation! :D $\endgroup$ Commented Dec 6, 2019 at 18:13
  • $\begingroup$ I'm confused why you think the coin change problem is not an optimization problem. It actually has a well-defined objective function that we are seeking to minimize (the number of coins) with a clear set of constraints (that add up to a given amount). $\endgroup$ Commented Apr 4, 2020 at 23:49
  • 1
    $\begingroup$ @AmelioVazquez-Reina By the Coin Change Problem, I mean the problem that asks us to count the number of ways of making an amount using some given denominations, and not minimize the number of coins used to make the amount. The link in the previous version of this answer leads to the latter. I've updated the link. $\endgroup$ Commented Apr 5, 2020 at 8:30
  • $\begingroup$ Thanks @ArkajyotiBanerjee, yes, the prev. link had confused me +1. $\endgroup$ Commented Apr 13, 2020 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.