如何高效求解带状态依赖收益的100层树状结构最优累计收益

现有一个100层的树状结构，每层每个节点包含3个选择（1、2、3），结构如下：

Layer 1             1                      2                3
                /    |     \
               /     |      \
              /      |       \
             /       |        \
Layer 2     1        2         3
          / | \    / | \     / | \   
Layer 3  1  2  3  1  2  3   1  2  3   ...
...

每个选择对应特定收益，且收益依赖前一节点的选择。需求为遍历所有自上而下的路径，找出其中的最高累计收益，无需获取具体路径。请问是否存在比使用for循环暴力遍历更高效的求解方法？

以下是我简化收益计算的尝试代码：

import numpy as np

# 层数
num_periods = 2

def get_payoffs(p):
    payoffs = np.array([[12, 6, 10],
                        [10, 24, 14],
                        [6, 10, 30]])
    return payoffs @ p

def get_prob(payoffs):
    nom = np.exp(payoffs)
    return nom/nom.sum()

p0 = np.eye(3)
p = p0
accumulated_payoffs = [0]
t = 1
while t<=num_periods:
    for i in range(len(accumulated_payoffs)):
        current_payoffs=[]
        for action in range(0,3):
            payoffs = get_payoffs(p[action])
            p[action]=get_prob(payoffs)
            current_payoffs.extend(payoffs+accumulated_payoffs[i])
        accumulated_payoffs[i] = current_payoffs
        t+=1
print(accumulated_payoffs)

核心优化思路：动态规划（DP） #

暴力遍历所有路径的时间复杂度是O(3^n)，当n=100时完全不可行。动态规划可以将复杂度降到O(n*3)，只需要维护每层每个选择的最大累计收益，无需保存所有路径。

动态规划逻辑：

1. 状态定义：设dp[t][a]表示第t层选择动作a（对应0/1/2，代表选择1/2/3）时的最大累计收益。
2. 初始状态：第1层的三个选择的收益（根据收益计算规则，初始时前一层无选择，对应p0单位矩阵的计算结果）。
3. 状态转移：对于第t层的每个动作a，其最大累计收益等于上一层所有动作的累计收益加上当前选择a对应收益的最大值，即：

   dp[t][a] = max(dp[t-1][0] + payoff_0a, dp[t-1][1] + payoff_1a, dp[t-1][2] + payoff_2a)
   

   其中payoff_ba表示前一层选b时，当前层选a的收益。
4. 最终结果：第100层三个dp[100][a]中的最大值就是所求的最高累计收益。

优化后的代码实现：

import numpy as np

# 层数
num_periods = 100

# 收益矩阵：payoff_matrix[b][a] 表示前一层选b，当前层选a的收益
payoff_matrix = np.array([[12, 6, 10],
                          [10, 24, 14],
                          [6, 10, 30]])

# 初始化：第1层的累计收益（对应初始p0单位矩阵的计算结果）
dp_prev = payoff_matrix.diagonal()

for _ in range(num_periods - 1):
    dp_current = np.zeros(3)
    for a in range(3):
        # 计算当前选a时，从上层所有选择过来的最大累计收益
        dp_current[a] = np.max(dp_prev + payoff_matrix[:, a])
    dp_prev = dp_current

# 最终最高累计收益
max_total_payoff = np.max(dp_prev)
print("最高累计收益：", max_total_payoff)

原代码的问题分析：

原代码试图保存所有路径的累计收益，当层数增加时，路径数量呈指数级增长（3^100），内存和计算资源都会直接耗尽。动态规划通过只保留每层的最优状态，彻底避免了指数级复杂度。

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