For dynamic programming problems, how do we know the subproblems will share subproblems?

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?

• 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.
– plop
Oct 27 '20 at 2:06
• cs.stackexchange.com/a/47221/755
– D.W.
Oct 27 '20 at 2:19
• (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.) Oct 27 '20 at 7:06
• @D.W. But where in the answer does it say how we can definitively say that the subproblems will overlap? Oct 27 '20 at 15:53
• 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. Oct 27 '20 at 16:07

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, 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).