使用动态规划实现数字三角形问题

好的，数字三角形问题可以用动态规划算法来解决。具体的做法是从三角形的底层开始，逐层向上计算最短路径和。

假设三角形有 n 层，第 i 层有 i 个数字，用 a[i][j] 表示第 i 层第 j 个数字。从三角形底部开始，设 f[i][j] 表示从第 i 行第 j 列出发到三角形底部的最小路径和，那么 f[i][j] 可以通过以下递推式计算得到：

f[i][j] = a[i][j] + min(f[i+1][j], f[i+1][j+1])

其中，a[i][j] 表示当前位置的数字，min(f[i+1][j], f[i+1][j+1])表示当前位置下一层相邻的两个数字中较小的那个数字的最小路径和。

最终，从三角形顶部到底部的最小路径和就是 f[1][1]。整个过程的时间复杂度为 O(n^2)。

下面是使用 Python 代码实现数字三角形问题的动态规划算法：

n = int(input())  # 三角形的行数
a = []  # 存储三角形数字的列表
for i in range(n):
    line = list(map(int, input().split()))
    a.append(line)

f = [[0] * n 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] = a[i][j]
        else:
            f[i][j] = a[i][j] + min(f[i+1][j], f[i+1][j+1])

print(f[0][0])  # 输出从三角形顶部到底部的最小路径和

希望能够帮助到你。