动态规划：为什么需要最优子结构
Dynamic Programming : Why the need for optimal sub structure
我正在重温我在 Dynamic Programming 上的笔记。它基本上是一种记忆递归技术，它存储了较小子问题的解决方案，以便以后在计算相对较大的子问题的解决方案时重用。
我的问题是为了将DP应用于递归问题，它必须有一个最优子结构。这基本上需要一个问题的最优解包含子问题的最优解。
还有可能吗？我的意思是你有没有见过一个问题的最优解不包含子问题的最优解的情况。
请分享一些例子，如果你知道加深我的理解。
根据我的理解，这个 'optimal substructure' 属性 不仅对于动态规划是必要的，而且对于首先获得解决方案的递归公式也是必要的。请注意，除了 Dynamic Programming, there is a separate article on the optimal substructure property. To make things even more involved, there is also an article about the Bellman equation.
上的维基百科文章外
您可以解决旅行商问题，每一步都选择最近的城市，但这是错误的方法。
在动态规划中 给定问题具有最优子结构属性如果给定问题的最优解可以通过以下方式获得使用其子问题的最优解。
例如最短路径问题有如下最优子结构属性:如果节点X位于从源节点U到目的节点V的最短路径上那么从U到V的最短路径是从U到X的最短路径和从X到V的最短路径的组合。
但是最长路径问题没有最优子结构属性。
即两个节点之间的最长路径不一定是中间节点之间的最长路径。
例如，最长路径q->r->t并不是q到r的最长路径和r到t的最长路径的组合，因为最长的从q到r的路径是q->s->t->r.
所以这里：一个问题的最优解不包含子问题的最优解。
更多详情请阅读
整个思路就是将问题缩小到相对较小的候选最优解集，然后用"brute force"来解决。
所以最好是较小的子问题的解决方案应该足以解决更大的问题。
这通过递归表示为较小子问题的最优解的函数。
回答这个问题：
Is it possible otherwise ? I mean have you ever seen a case where
optimal solution to a problem does not contain an optimal solution to
subproblems.
不，这不可能，甚至可以证明。
你可以尝试对任何递归问题实现动态规划，但如果它没有最优子结构，你将不会得到更好的结果属性。换句话说，动态规划方法对于解决没有最优子结构 属性 的问题没有用处。
你完全正确，定义不精确。 DP 是一种获得算法加速的技术，而不是算法本身。术语 "optimal substructure" 是一个模糊的概念。 （你又对了！）也就是说，每个循环都可以表示为一个递归函数：每次迭代都解决了后续问题的一个子问题。每个带有循环的算法都是DP吗？显然不是。
人们所说 "optimal substructure" 和 "overlapping subproblems" 的实际意思是子问题结果的使用 足以降低解决方案的渐近复杂性 。换句话说，memoization 很有用！在大多数情况下，微妙的含义是从指数时间减少到多项式时间，O(n^k) 到 O(n^p)，p
Ex：密集图中两个节点之间的路径数量呈指数级增长。 DP只看其中的一个多项式数就找到了最短路径，因为备忘录在这种情况下非常有用。
另一方面，Travelling salesman 可以表示为一个 memoized 函数（例如，参见 this discussion），其中 memos 导致 O( (1/2)^n ) 倍的时间被保存.但是，通过 n 个城市的 TS 路径的数量是 O(n!)。这要大得多，以至于渐近 运行 时间仍然是超指数的：O(n!)/O(2^n) = O(n!)。这样的算法通常不称为动态程序，即使它遵循与最短路径 DP 非常相同的模式。看来只有成绩好才算DP！
我正在重温我在 Dynamic Programming 上的笔记。它基本上是一种记忆递归技术，它存储了较小子问题的解决方案，以便以后在计算相对较大的子问题的解决方案时重用。
我的问题是为了将DP应用于递归问题，它必须有一个最优子结构。这基本上需要一个问题的最优解包含子问题的最优解。
还有可能吗？我的意思是你有没有见过一个问题的最优解不包含子问题的最优解的情况。
请分享一些例子，如果你知道加深我的理解。
根据我的理解，这个 'optimal substructure' 属性 不仅对于动态规划是必要的，而且对于首先获得解决方案的递归公式也是必要的。请注意，除了 Dynamic Programming, there is a separate article on the optimal substructure property. To make things even more involved, there is also an article about the Bellman equation.
上的维基百科文章外您可以解决旅行商问题，每一步都选择最近的城市，但这是错误的方法。
在动态规划中 给定问题具有最优子结构属性如果给定问题的最优解可以通过以下方式获得使用其子问题的最优解。
例如最短路径问题有如下最优子结构属性:如果节点X位于从源节点U到目的节点V的最短路径上那么从U到V的最短路径是从U到X的最短路径和从X到V的最短路径的组合。
但是最长路径问题没有最优子结构属性。 即两个节点之间的最长路径不一定是中间节点之间的最长路径。
例如，最长路径q->r->t并不是q到r的最长路径和r到t的最长路径的组合，因为最长的从q到r的路径是q->s->t->r.
所以这里：一个问题的最优解不包含子问题的最优解。
更多详情请阅读
整个思路就是将问题缩小到相对较小的候选最优解集，然后用"brute force"来解决。
所以最好是较小的子问题的解决方案应该足以解决更大的问题。
这通过递归表示为较小子问题的最优解的函数。
回答这个问题：
Is it possible otherwise ? I mean have you ever seen a case where optimal solution to a problem does not contain an optimal solution to subproblems.
不，这不可能，甚至可以证明。
你可以尝试对任何递归问题实现动态规划，但如果它没有最优子结构，你将不会得到更好的结果属性。换句话说，动态规划方法对于解决没有最优子结构 属性 的问题没有用处。
你完全正确，定义不精确。 DP 是一种获得算法加速的技术，而不是算法本身。术语 "optimal substructure" 是一个模糊的概念。 （你又对了！）也就是说，每个循环都可以表示为一个递归函数：每次迭代都解决了后续问题的一个子问题。每个带有循环的算法都是DP吗？显然不是。
人们所说 "optimal substructure" 和 "overlapping subproblems" 的实际意思是子问题结果的使用 足以降低解决方案的渐近复杂性 。换句话说，memoization 很有用！在大多数情况下，微妙的含义是从指数时间减少到多项式时间，O(n^k) 到 O(n^p)，p Ex：密集图中两个节点之间的路径数量呈指数级增长。 DP只看其中的一个多项式数就找到了最短路径，因为备忘录在这种情况下非常有用。 另一方面，Travelling salesman 可以表示为一个 memoized 函数（例如，参见 this discussion），其中 memos 导致 O( (1/2)^n ) 倍的时间被保存.但是，通过 n 个城市的 TS 路径的数量是 O(n!)。这要大得多，以至于渐近 运行 时间仍然是超指数的：O(n!)/O(2^n) = O(n!)。这样的算法通常不称为动态程序，即使它遵循与最短路径 DP 非常相同的模式。看来只有成绩好才算DP！