0
$\begingroup$

So, a common reasoning to use dynamic programming as the website (https://www.tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm) mentions is that, we use dynamic programming when:

Dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems.

So my question is that how do we know when in a problem if we apply the divide-and-conquer approach, we will get overlapping sub-problems?

Eg: Let's take the famous problem from Cormen.

A car factory has two assembly lines, each with n stations. A station is denoted by Si,j where i is either 1 or 2 and indicates the assembly line the station is on, and j indicates the number of the station. The time taken per station is denoted by ai,j. Each station is dedicated to some sort of work like engine fitting, body fitting, painting, and so on. So, a car chassis must pass through each of the n stations in order before exiting the factory. The parallel stations of the two assembly lines perform the same task. After it passes through station Si,j, it will continue to station Si,j+1 unless it decides to transfer to the other line. Continuing on the same line incurs no extra cost, but transferring from line i at station j – 1 to station j on the other line takes time ti,j. Each assembly line takes an entry time ei and exit time xi which may be different for the two lines. Give an algorithm for computing the minimum time it will take to build a car chassis.

Here, how do we know that subproblems will overlap?

$\endgroup$
  • $\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$ – plop Oct 27 '20 at 2:06
  • $\begingroup$ cs.stackexchange.com/a/47221/755 $\endgroup$ – D.W. Oct 27 '20 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$ – greybeard Oct 27 '20 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$ – user123215321631443 Oct 27 '20 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$ – j_random_hacker Oct 27 '20 at 16:07
2
$\begingroup$

The answer is - you don't. Not in advance. There are no guarantees and there is no silver bullet process.

Instead, dynamic programming is a way of thinking about a problem, a framework for approaching a problem. You typically won't know whether that approach will be successful or not in advance.

Dynamic programming basically amounts to finding a recursive algorithm for the problem, and then speeding it up with memoization. You'll have to try different recursive algorithms (different ways of decomposing into subproblems) and see, for each candidate, if it has the properties that are needed to apply these ideas successfully. You usually won't know in advance whether any particular decomposition into subproblems will be successful. You might be able to tell whether those subproblems will be "overlapping", but not whether it'll lead to a useful dynamic programming algorithm. It's partly an art, where experience helps give you some intuitions for what kinds of subproblems might be useful in any particular situation.

I encourage reading What is dynamic programming about?, When can I use dynamic programming to reduce the time complexity of my recursive algorithm?, and Deciding on Sub-Problems for Dynamic Programming to get a sense of this perspective.

Personal opinion: I personally don't find "overlapping subproblems" as a very helpful way to think about dynamic programming. I encourage you to use whatever works for you, but that one never worked very well for me. If you want to understand it, think about algorithms that work on an array $A[1..n]$. Divide-and-conquer will work on some subarrays, say $A[1..n/2],A[n/2+1..n],\ldots$, but no pair of those have a partial overlap. Dynamic programming may work on all subarrays, say $A[i..j]$ for all $i<j$, and there are pairs of those that partly overlap (e.g., $A[3..5]$ overlaps with $A[4..9]$). That's what is meant by "overlapping subproblems", and that is one distinction between dynamic programming vs divide-and-conquer. That said, I don't find that a very helpful characterization, personally -- and especially, I don't find it helpful at designing an algorithm (it might be more helpful once I already have an algorithm and am wondering whether I should call it divide-and-conquer vs dynamic programming, but at that point I often don't care too much what we call it).

$\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.