动态规划之数塔问题python

动态规划是一种常用的算法思想，用于解决具有重叠子问题和最优子结构性质的问题。数塔问题是动态规划中的一个经典问题，它可以用来求解从塔顶到塔底的最大路径和。

在数塔问题中，给定一个由整数组成的数塔，从塔顶出发，在每一层只能选择相邻的两个数字中的一个数字，向下走到下一层，直到走到塔底。要求找出一条路径，使得路径上经过的数字之和最大。

以下是数塔问题的Python实现：

def max_path_sum(tower):
    n = len(tower)
    dp = [ * n for _ in range(n)]  # 创建一个二维数组dp，用于保存每个位置的最大路径和

    # 初始化最后一行
    for i in range(n):
        dp[n-1][i] = tower[n-1][i]

    # 从倒数第二行开始逐层向上计算最大路径和
    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 = [
    ,
    [12, 15],
    [10, 6, 8],
    [2, 18, 9, 5],
    [19, 7, 10, 4, 16]
]

max_sum = max_path_sum(tower)
print("最大路径和为:", max_sum)