动态规划中子问题的独立性是一个问题吗？
Is independence of subproblems in dynamic programming an issue?
在阅读 CLRS 第 15.3 节“何时应该使用动态规划”。在解释 Optimal substructure 时他们举了两个例子，它们是未加权的最长简单路径和未加权的最短路径。
他们说，
The subproblems in finding the longest simple path are not independent, whereas for shortest paths they
这就是为什么我们不能使用动态规划求解未加权的最长简单路径，我对此没有任何问题，但他们也说
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.
最后一句话
independence of subproblems is not an issue.
子问题的独立性是不是问题？如果不是问题那么为什么他们说第一句话或者我只是误解了一些东西。
问题是您不能简单地合并两个相关子问题的答案。
如果问题是独立的，那很好。如果你只看一个子问题，同样没问题。但是如果你需要组合 2 个答案并且它们是依赖的，你必须保持一些额外的状态。
在最长的简单路径的情况下，“一些额外的状态”可能会成倍增加。 :-)
在阅读 CLRS 第 15.3 节“何时应该使用动态规划”。在解释 Optimal substructure 时他们举了两个例子，它们是未加权的最长简单路径和未加权的最短路径。
他们说，
The subproblems in finding the longest simple path are not independent, whereas for shortest paths they
这就是为什么我们不能使用动态规划求解未加权的最长简单路径，我对此没有任何问题，但他们也说
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.
最后一句话
independence of subproblems is not an issue.
子问题的独立性是不是问题？如果不是问题那么为什么他们说第一句话或者我只是误解了一些东西。
问题是您不能简单地合并两个相关子问题的答案。
如果问题是独立的，那很好。如果你只看一个子问题，同样没问题。但是如果你需要组合 2 个答案并且它们是依赖的，你必须保持一些额外的状态。
在最长的简单路径的情况下，“一些额外的状态”可能会成倍增加。 :-)