数字三角形动态规划

数字三角形是一个由数字组成的三角形，其中每个数字都与其下方相邻的两个数字相连。现在有一个数字三角形，要求从三角形的顶端出发，到达底端，使所经过的数字之和最大。这个问题可以使用动态规划来解决。

具体的动态规划算法如下：

1. 定义状态：设 $f(i,j)$ 表示从三角形的第 $i$ 行第 $j$ 列出发，到达底端，所经过的数字之和的最大值。

2. 初始化状态：$f(n,j)=a_{n,j}$，其中 $n$ 表示数字三角形的行数，$a_{n,j}$ 表示数字三角形第 $n$ 行第 $j$ 列的数字。

3. 状态转移：对于三角形中的任意一个位置 $(i,j)$，其下方相邻的两个数字为 $(i+1,j)$ 和 $(i+1,j+1)$，则状态转移方程为：

$$f(i,j)=\max\{f(i+1,j),f(i+1,j+1)\}+a_{i,j}$$

4. 最终答案：$f(1,1)$ 即为所求。

代码实现如下：

def maximum_sum(triangle):
    n = len(triangle)
    f = [[0] * (i+1) for i in range(n)]
    for i in range(n-1, -1, -1):
        for j in range(i+1):
            if i == n-1:
                f[i][j] = triangle[i][j]
            else:
                f[i][j] = max(f[i+1][j], f[i+1][j+1]) + triangle[i][j]
    return f[0][0]

其中，输入的 `triangle` 是一个由数字组成的二维列表，表示数字三角形。函数返回所经过的数字之和的最大值。