5、数字三角形问题 从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。 回溯法

数字三角形问题可以通过回溯算法来解决。具体做法是，从三角形的顶部开始，递归地向下搜索每一条可能的路径，每次只能向左或向右移动一步。在搜索的过程中，需要记录当前路径的和以及当前所在的位置，如果到达底层则更新最大值并返回。如果当前路径的和已经小于等于最大值，则可以剪枝，不再继续搜索。

以下是一个基于回溯算法的Python代码实现：

max_sum = float('-inf')

def dfs(triangle, i, j, cur_sum):
    global max_sum
    if i == len(triangle):
        max_sum = max(max_sum, cur_sum) # 更新最大值
        return
    if cur_sum + triangle[i][j] <= max_sum: # 剪枝
        return
    dfs(triangle, i+1, j, cur_sum+triangle[i][j]) # 向左移动
    dfs(triangle, i+1, j+1, cur_sum+triangle[i][j]) # 向右移动

triangle = [
    [5],
    [8, 4],
    [3, 6, 9],
    [7, 2, 5, 1],
    [9, 4, 3, 8, 7]
]
dfs(triangle, 0, 0, 0)
print(max_sum)

在上述代码中，我们使用了一个全局变量`max_sum`来记录最大路径和。`dfs`函数接收当前所在位置的行数`i`、列数`j`，以及当前路径的和`cur_sum`作为参数。如果到达底层，则更新最大值并返回；否则，向左或向右移动一步，并继续搜索。在搜索的过程中，如果当前路径的和已经小于等于最大值，则剪枝，不再继续搜索。最终输出得到的最大路径和即可。

该算法的时间复杂度为$O(2^n)$，其中$n$为三角形的高度。因为在最坏情况下，需要搜索所有的路径。