我想了解这个问题是如何显示最优子结构的:
问题:给定任何一棵只有正整数作为节点的二叉树，你如何找到一个不相交的子集(由它们之间没有边的节点组成)来实现最大可能的乘积?
到目前为止，我已经确定，因为节点只能是正的，所以最大的乘积要么是尽可能多的节点相乘的结果，选择具有较高值的节点相乘，或者两者之间的某种组合。如果我要处理第一个解，我可以从最低层开始，从其他每层取节点。然而，这并没有显示出最优子结构。任何提示将不胜感激!
选择rootR如果给定的树是自由(无根)树
我们在树T上定义函数F(R)为具有R为其元素的所有有效节点集合中乘积最大的节点集合。这里的Valid是指"由没有边的节点组成"。
同样，我们在树T上定义与F(R)相似的函数H(R)，但是在集合上没有R作为它的元素之一。
我们可以声明节点O的最优集合可以(或不)有节点R作为其元素之一。
-
如果R∈O然后一组最优的节点O是
{R, H (R.children [0]), H (R.children[1]),…， H(R.children[R.children.size() - 1])}，其中H(R.children[i])是在以R.children[i]为根的子树上定义的。因为R在O中被选中，它的所有子节点都不属于O，并且H(R.children[i])中节点的乘法大于或等于O中属于R.children[i]定义的子树的节点的乘法。由于每个子树的答案都独立于其他子树的答案，并且O是最优的，我们知道H(R.children[i])中节点的乘法小于或等于O中属于R.children[i]定义的子树的节点的乘法。那么O'也是最优的。 -
如果R∉O然后一组最优的节点O是
{R,马克斯(F (R.children [0]), H (R.children[0])),马克斯(F (R.children [1]), H (R.children[1])),…， max(F(R.children[R.children.size() - 1])， H(R.children[R.children.size() - 1])}，其中F(R.children[i])和H(R.children[i])是在以R.children[i]为根的子树上定义的。或多或少与#1相同的解释，但由于R没有在O上被选中，那么R的任何子树都可以在其子树上被选中(或不被选中)。
由于最优选择是未知的，那么答案是max(F(R)， H(R)，因为在最优集合中选择R只有两种可能的情况。
根据维基百科，"如果一个问题可以通过将其分解成子问题，然后递归地找到子问题的最优解来最优地解决，那么它就被称为具有最优子结构。">
我们似乎有一个明确的案例将这个问题分解成子问题并递归地解决。设t为函数求值的当前节点。如果我们包括t，我们不能包括它的任何子节点，所以我们用它的值乘以孙子节点的结果作为参数;否则，我们将子节点的结果相乘作为参数。一般:
f(t) = max(
value(t) * product(f(g)),
product(f(c))
)
where g is a granchild of t
c is a child of t