Independence property of sub problems for dynamic programming techniques to apply

Question

Two criteria for an algorithm to be solved by dynamic programming technique is

1. Sub problems should be independent.
2. Sub problems should overlap .

I think I understand what overlapping means . It basically means that the subproblems have subsubproblems that may be the same . So instead of solving the subsubproblem over and over again we solve it once, put it in a hashtable or array and can look it up the nest time it is required . But what does point 1 ie independence of subproblems mean here ? If they have some common subsubproblems how can we call them to be independent? I mean it sounds very much counterintuitive to me at this stage .

Edit: This crtiteria is actually given in the famous book: Introduction to Algorithms by CLRS in the Dynamic Programming chapter.

Answer 1

Please tell us where you are reading that DP applies to problems with overlapping and independent sub-problems. I don't think that's correct, for the same intuitive reason you give-- if the problems overlap, they aren't independent.

I usually see independent sub-problems given as a criterion for Divide-And-Conquer style algorithms, while I see overlapping sub-problems and optimal sub-structure given as criteria for the Dynamic Programming family. (Intuitively, optimal substructure means that the best solution of a larger problem is composed of the best solutions of sub-problems. The classic example is the shortest path in a graph problem: If you know that the shortest path from A to B goes through C, then you also know that the part of the shortest path from A to B that goes through C happens to be the shortest path from A to C.)

UPDATE: Oh, I see-- yes, I guess they do mention independence. But I don't read that with the same emphasis that you are. Meaning, they mention independence in the context of, or as a way of understanding, the larger and more important concept of optimal substructure.

What they mean specifically by independence is that even if two problems overlap, they are "independent" in the sense that they don't interact-- the solution to one does not really depend on the solution to the other. They actually use the same example I did, the shortest path. Sub-problems of the shortest path problem are smaller shortest path problems that are independent: If the shortest path from A to B goes through C, then the shortest path from A to C doesn't use any edges in the shortest path from C to B. The longest path problem, by contrast, does not share that independence of sub-problems.

I don't think CLRS are wrong to bring up independence, but I do think the language they're using is a little ambiguous.