Is independence of subproblems in dynamic programming an issue?

Question

While reading CLRS section 15.3 about "When I should use dynamic programming." and during the explanation of Optimal substructure they gave 2 examples, they are unweighted longest simple path and unweighted shortest path.

They said,

The subproblems in finding the longest simple path are not independent, whereas for shortest paths they

That's why we can't solve unweighted longest simple path using dynamic programming and I don't have any problem with that but they also said

Both problems examined in Sections 15.1 and 15.2 have independent subproblems ...... In rod cutting, to determine the best way to cut up a rod of length n, we look at the best ways of cutting up rods of length I for I = 0, 1,..., n-1. Because an optimal solution to the length -n problem includes just one of these subproblem solutions (after we have cut off the first piece), independence of subproblems is not an issue.

The last sentence

independence of subproblems is not an issue.

Is the independence of subproblems an issue or not? and If not an issue so why they said the first quote or I'm just me misunderstanding something.

Answer 1

The problem is that you cannot simply merge the answers to two dependent subproblems.

If problems are independent, that is fine. If you only look at one subproblem, likewise that is fine. But if you need to combine 2 answers and they are dependent, you have to maintain some additional state.

Where, as in the case of the longest simple path, "some additional state" may blow up on you exponentially. :-)