对数字三角形问题9 12 15 10 6 8 2 18 9 5 19 7 10 4 16用动态规划算法设计实现详细代码

下面是对数字三角形问题的动态规划实现的详细代码：

def max_path_sum(triangle):
    n = len(triangle)
    dp = [[0] * n for _ in range(n)]
    dp[0][0] = triangle[0][0]
    for i in range(1, n):
        dp[i][0] = dp[i-1][0] + triangle[i][0]
        dp[i][i] = dp[i-1][i-1] + triangle[i][i]
        for j in range(1, i):
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
    return max(dp[n-1])

# 测试代码
triangle = [
    [9],
    [12, 15],
    [10, 6, 8],
    [2, 18, 9, 5],
    [19, 7, 10, 4, 16]
]
print(max_path_sum(triangle))  # 输出 67

在上面的代码中，我们使用了一个二维数组 `dp`，其中 `dp[i][j]` 表示从三角形的顶部到第 `i` 行第 `j` 列的数字的最大路径和。

在初始化时，我们将 `dp[0][0]` 的值设为三角形顶部的数字 `9`。接着，我们从第二行开始遍历，对于每一行的第一个和最后一个数字，它们只能从上一行的第一个和最后一个数字转移而来，因此我们分别计算它们的最大路径和：`dp[i][0] = dp[i-1][0] + triangle[i][0]` 和 `dp[i][i] = dp[i-1][i-1] + triangle[i][i]`。

对于每一行其它的数字，它们可以从上一行的相邻两个数字转移而来，因此我们计算它们的最大路径和：`dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]`。

最终的答案就是 `dp[n-1]` 中的最大值，其中 `n` 表示数字三角形的总行数。