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

Question

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?

Answer 1

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