Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

6
  • $\begingroup$ Did you decide already what you'll call a subproblem? In many cases more than subproblems what you find are smaller versions of the same problem and these are related by a recurrence relation. The overlap then consists in the recurrence relation requiring the value of one of the smaller copies of the problem to define the value of a few of the larger versions. $\endgroup$ Commented Oct 27, 2020 at 2:06
  • $\begingroup$ cs.stackexchange.com/a/47221/755 $\endgroup$ Commented Oct 27, 2020 at 2:19
  • $\begingroup$ (Welcome to COMPUTER SCIENCE @SE. The common way to "mark down" larger blocks of external material included for convenience is as a block quote: prepend > to "each line" or mark and use "the " button". Credit where possible.) $\endgroup$ Commented Oct 27, 2020 at 7:06
  • $\begingroup$ @D.W. But where in the answer does it say how we can definitively say that the subproblems will overlap? $\endgroup$ Commented Oct 27, 2020 at 15:53
  • $\begingroup$ You don't know that. When faced with a computational problem, if you want to solve it using DP, your task is to think of a way to decompose it into subproblems so that the subproblems share subproblems. If you can do this, you can apply the technique of DP (and hopefully get an efficient algorithm). How to choose the right way to to break the problem into subproblems, i.e., into subproblems that have this overlapping substructure? There is no mechanical process for that. All you can do is study how some example problems have been solved, and develop your intuition. $\endgroup$ Commented Oct 27, 2020 at 16:07