数字三角形问题 python

数字三角形问题是一个经典的动态规划问题。假设有一个数字三角形，如下所示：

   7
  3 8
 8 1 0
2 7 4 4

从三角形的顶部开始，每次可以向下走一步或者向右下走一步，一直走到三角形的底部。路径上经过的数字累加起来，求出从顶部到底部的路径中数字总和的最大值。

解决这个问题的关键是设计一个递推公式来计算每个位置的最大值。假设 $dp[i][j]$ 表示从顶部到位置 $(i,j)$ 的路径中数字总和的最大值，$a[i][j]$ 表示位置 $(i,j)$ 的数字，则有：

$$ dp[i][j] = a[i][j] + \max(dp[i-1][j], dp[i-1][j-1]) $$

其中，$i>0$ 且 $0<j<i$，$dp[0][0] = a[0][0]$。

根据这个递推公式，我们可以使用一个二维数组 $dp$ 来记录每个位置的最大值。最终，$dp[n-1][j]$ 中的最大值就是从顶部到底部的路径中数字总和的最大值。

以下是一个使用 Python 实现的数字三角形问题的代码：

n = 4
a = [
    [7, 0, 0, 0],
    [3, 8, 0, 0],
    [8, 1, 0, 0],
    [2, 7, 4, 4],
]
dp = [[0] * n for _ in range(n)]
dp[0][0] = a[0][0]
for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            dp[i][j] = a[i][j] + dp[i-1][j]
        elif j == i:
            dp[i][j] = a[i][j] + dp[i-1][j-1]
        else:
            dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i-1][j-1])
print(max(dp[n-1]))

输出结果为：`30`，即从顶部到底部的路径中数字总和的最大值为 30。