动态规划数塔问题 python

动态规划是一种常用的算法思想，用于解决具有重叠子问题和最优子结构性质的问题。而数塔问题是动态规划中的一个经典问题，它通常描述为一个由数字组成的塔状结构，从塔的顶部出发，每次只能向下走到相邻的数字，直到走到塔底，要求找出一条路径使得路径上经过的数字之和最大。

在Python中，可以使用动态规划来解决数塔问题。具体步骤如下：

1. 定义一个二维数组dp，dp[i][j]表示从塔顶走到第i行第j列时的最大路径和。
2. 初始化dp数组的最后一行为数塔的最后一行。
3. 从倒数第二行开始，逐行向上计算dp数组的值。对于每个位置dp[i][j]，可以选择向下走到dp[i+1][j]或者向下走到dp[i+1][j+1]，取两者中较大的值与当前位置的数字相加，更新dp[i][j]。
4. 最终，dp即为所求的最大路径和。

下面是一个示例代码：

def max_path_sum(tower):
    n = len(tower)
    dp = [ * n for _ in range(n)]
    
    # 初始化最后一行
    for j in range(n):
        dp[n-1][j] = tower[n-1][j]
    
    # 逐行向上计算
    for i in range(n-2, -1, -1):
        for j in range(i+1):
            dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + tower[i][j]
    
    return dp

# 示例输入
tower = [
    ,
    [8, 3],
    [12, 7, 16],
    [4, 10, 11, 6]
]

# 调用函数并输出结果
result = max_path_sum(tower)
print("最大路径和为:", result)