正整数节点二叉树最大乘积不相交子集的最优子结构求解

这个问题属于树形动态规划的典型场景，你之前尝试的隔层选取方案之所以无法体现最优子结构，本质是用全局统一的选取规则替代了每个子树独立的最优决策空间，具体的最优子结构逻辑如下：

最优子结构的核心逻辑 #

最优子结构的核心要求是：问题的全局最优解可以通过组合其子问题的最优解得到。对这个问题而言，任意子树的最大乘积解，仅由它的左右子树的两类最优状态推导而来，不需要感知子树内部的具体选取方案。

子问题的状态定义 #

对任意以节点u为根的子树，我们只需要维护两个互斥的最优状态：

• dp[u][0]：不选取根节点u时，该子树能得到的最大乘积
• dp[u][1]：选取根节点u时，该子树能得到的最大乘积

状态转移规则（直接体现最优子结构） #

因为所有节点值都是正整数，乘积天然具有单调性，所以状态转移不需要考虑负收益的情况，规则如下：

1. 若选取根节点u，则其左右子节点都不能被选取，此时当前子树的最大乘积为根节点值 × 左子树不选根的最大乘积 × 右子树不选根的最大乘积，公式为：
   dp[u][1] = val[u] * dp[left_child_u][0] * dp[right_child_u][0]
2. 若不选取根节点u，则左右子节点都可以自由选择选或不选，我们只需要取每个子树两个状态中的最大值相乘即可，公式为：
   dp[u][0] = max(dp[left_child_u][0], dp[left_child_u][1]) * max(dp[right_child_u][0], dp[right_child_u][1])

可以看到，当前子树的两个最优状态，完全由左右子树的最优状态组合得到，只要左右子树的dp值是各自子问题的最优解，组合出来的当前子树的dp值就一定是当前子问题的最优解，这就是该问题最优子结构的直接体现。

隔层选取方案的局限性 #

隔层选取本质是预设了全局的奇偶层选取规则，无法适配局部子树的最优决策，举个简单反例：

根节点值为2，左孩子值为10，左孩子的两个子节点值均为2
如果按隔层选取，选根+两个孙节点的乘积是2*2*2=8，选左孩子的乘积是10，明显后者更优，这种局部更优的决策只能通过每个子树独立计算两种状态的方式得到，也就是我们上面说的最优子结构的应用。

整棵树的最终最大乘积就是根节点两个状态的最大值：max(dp[root][0], dp[root][1])。

内容的提问来源于stack exchange，提问作者coco