本文介绍一种基于动态规划思想的广度优先搜索（bfs）方法，在每层节点收益依赖于上一层选择的多叉树中，以线性时间复杂度 o(n) 找出从根到叶的最大累积收益值（无需返回具体路径）。
在您描述的场景中，树具有 100 层、每个节点有 3 个子节点（动作 1/2/3），且当前节点的收益并非固定值，而是依赖于其父节点所选动作——这本质上是一个状态转移问题：从父状态 a_{t−1} 到子状态 a_t 的收益为 reward(a_{t−1}, a_t)。此类结构常见于马尔可夫决策过程（MDP）的展开树或序列决策模型中。
直接枚举所有 3^100 条路径显然不可行（指数爆炸）。但注意到：最优子结构性质依然成立——任意节点 v 为根的子树中的最大累积收益，等于 v 自身的（依赖父动作的）收益，加上其所有子节点中对应子树的最大累积收益。因此，我们可采用自顶向下逐层动态规划（即 BFS 或迭代式 DP），仅维护到达每一层各状态的最大累积收益，而非完整路径。
具体算法如下（时间复杂度 O(n)，n 为总节点数）：
- 初始化：根层（Layer 1）有 3 个节点，设其初始累积收益为 dp[0][a] = 0（因无父动作，可约定起始收益为 0；实际中若根节点有基础收益，可在此处初始化）；
- 对每一层 t（从 1 到 99）：
- 创建新数组 dp_next[a] = −∞（a ∈ {0,1,2}）；
- 对每个父动作 prev_a，计算其子动作 curr_a 的即时收益 r = reward(prev_a, curr_a)；
- 更新：dp_next[curr_a] = max(dp_next[curr_a], dp[prev_a] + r)；
- 最终结果为 max(dp_last)，即第 100 层所有节点累积收益的最大值。
示例伪代码（Python 风格，假设 reward(prev, curr) 函数已定义）：
def max_cumulative_reward(num_layers, reward_func):
# dp[a] 表示到达当前层动作 a 时的最大累积收益
dp = [0.0, 0.0, 0.0] # Layer 1 初始状态
for layer in range(1, num_layers): # 从第1层（索引0）走到第num_layers-1层
dp_next = [-float('inf')] * 3
for prev_a in range(3):
for curr_a in range(3):
r = reward_func(prev_a, curr_a)
dp_next[curr_a] = max(dp_next[curr_a], dp[prev_a] + r)
dp = dp_next
return max(dp)
# 示例 reward_func：依赖前序动作的收益矩阵（3x3）
payoff_matrix = np.array([
[12, 6, 10], # prev=0 → curr=[0,1,2]
[10, 24, 14], # prev=1 → curr=[0,1,2]
[6, 10, 30] # prev=2 → curr=[0,1,2]
])
reward_func = lambda prev, curr: payoff_matrix[prev, curr]
print(max_cumulative_reward(100, reward_func)) # O(100×9) = O(900) 次运算
⚠️ 注意事项：
- 原始代码中混用了概率更新（get_prob）、矩阵乘法与路径枚举逻辑，偏离了最优化目标；本方案剥离非必要计算，聚焦收益传播；
- 若收益函数 reward(prev, curr) 具有特殊结构（如稀疏性、单调性），可进一步剪枝，但最坏情况下 O(n) 是理论下界——必须访问每个边至少一次；
- 此方法天然支持任意分支因子（不限于 3）和不等深树，只需调整内层循环范围；
- 如需返回最优路径，只需在 dp_next 更新时同步记录回溯指针（parent[curr_a] = prev_a），空间开销仅增 O(层深)。
综上，面对状态依赖型多层决策树，放弃穷举，转而采用逐层动态规划的 BFS 策略，是兼顾效率、正确性与可扩展性的最优解。