本文介绍一种基于动态规划思想的广度优先搜索（bfs）算法，用于在每层有3个分支、共100层、且节点收益依赖于父节点选择的树中，以 o(n) 时间复杂度求得最大累积收益值（无需返回具体路径）。
在该问题中，树具有明确的层级结构（100 层），每个非叶节点恰好有 3 个子节点（动作选择：1、2、3），且任一节点的即时收益不仅由自身动作决定，还依赖于其父节点所选动作——即存在状态转移依赖关系。这排除了简单贪心或静态查表法，但并未破坏最优子结构性质：从根到某节点的最优累积收益，必然等于其父节点的最优累积收益，加上该节点在对应父动作约束下的最大可能收益。
因此，我们可采用自顶向下的动态规划策略，配合 BFS 遍历实现高效计算：
- 维护一个队列，存储 (node_id, parent_action, cumulative_payoff) 元组；
- 初始时将根节点的三种可能动作及其初始收益入队（注意：根无父节点，其收益为预定义基准值）；
- 每次出队一个节点，根据其 parent_action 查表计算其三个子动作的即时收益，更新子节点的累积收益，并将子节点入队；
- 同时维护全局变量 max_cumulative，实时更新最大值；
- 遍历完成后直接返回 max_cumulative。
该方法时间复杂度为 O(N)，其中 N 是树中总节点数（≈ 3¹⁰⁰，但实际只需遍历一次所有节点）；空间复杂度为 O(W)，W 为最大层宽（即 BFS 队列峰值长度，最坏为 3⁹⁹，但可通过逐层处理优化为 O(3ˡ)）。
⚠️ 注意事项：
- 原始代码中混用了概率传播（get_prob）、矩阵乘法与循环逻辑，偏离了核心优化目标，且存在 t 递增位置错误、accumulated_payoffs 结构混乱等问题，不适用于本题；
- 实际实现时应避免显式构建整棵树（内存爆炸），而采用“按层生成+滚动更新”方式：仅保存当前层各节点的最优累积收益（长度为 3ˡ），再据此计算下一层；
- 若收益函数 get_payoffs(prev_action) 返回的是一个长度为 3 的数组（对应子动作 1/2/3 的收益），则第 l 层的状态可表示为 dp[l][a] = max_{prev_a} { dp[l-1][prev_a] + payoff(prev_a, a) }，即标准的二维 DP 转移，空间可压缩至 O(3)。
def find_max_cumulative_payoff(num_layers, payoff_func):
# payoff_func(prev_action) -> [payoff_for_action1, payoff_for_action2, payoff_for_action3]
if num_layers == 0:
return 0
# dp[a] = max cumulative payoff ending with action 'a' at current layer
dp = [0.0, 0.0, 0.0] # layer 0 (root): no parent, assume base payoff = 0
for layer in range(1, num_layers):
new_dp = [-float('inf')] * 3
for prev_a in range(3):
payoffs = payoff_func(prev_a) # list of 3 floats
for a in range(3):
new_dp[a] = max(new_dp[a], dp[prev_a] + payoffs[a])
dp = new_dp
return max(dp)
# 示例：定义状态依赖收益函数
def example_payoff(prev_action):
# 简化示例：prev_action=0 → 子动作收益为[5, 8, 2]；以此类推
table = {
0: [5, 8, 2],
1: [7, 3, 9],
2: [1, 6, 4]
}
return table[prev_action]
print(find_max_cumulative_payoff(100, example_payoff)) # O(100×9) = O(1)综上，面对深度大、分支固定、收益具马尔可夫依赖性的树形决策问题，逐层动态规划 + 状态压缩是最优解法：它规避了指数级路径枚举，利用最优子结构剪除无效计算，将复杂度从 O(3¹⁰⁰) 降至线性级别，是理论最优且工程可行的标准方案。
