### 使用Python实现数字三角形问题的动态规划算法 以下是基于动态规划思想解决数字三角形问题的一个典型代码示例。该程序通过自底向上的方式计算从顶部到底部的最大路径和。 #### 自底向上动态规划解决方案 ```python def max_path_sum(triangle): # 从倒数第二行开始，逐步更新每一层的最大值 for i in range(len(triangle) - 2, -1, -1): # 遍历从倒数第二行到第一行 for j in range(len(triangle[i])): # 更新当前行的每一个元素 triangle[i][j] += max(triangle[i + 1][j], triangle[i + 1][j + 1]) # 当前位置加上其子节点中的最大值 return triangle[0][0] # 返回顶点处存储的最大路径和 # 输入样例：一个数字三角形 triangle = [ [7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5] ] result = max_path_sum(triangle) print(result) # 输出最大路径和 ``` 此代码的核心逻辑是从底部逐层向上累加每一条可能路径的最大值，最终得到整个三角形的最大路径和[^3]。 --- #### 帕斯卡三角形生成作为补充说明 虽然上述代码解决了数字三角形的最大路径和问题，但如果需要生成类似于帕斯卡三角形的数据结构，则可参考以下函数： ```python def generate_pascals_triangle(rows): triangle = [[1]] for i in range(1, rows): new_row = [1] for j in range(1, i): new_row.append(triangle[i - 1][j - 1] + triangle[i - 1][j]) new_row.append(1) triangle.append(new_row) return triangle def print_triangle(triangle): width = len(" ".join(map(str, triangle[-1]))) for row in triangle: print(" ".join(map(str, row)).center(width)) # 测试生成并打印帕斯卡三角形 pascal_triangle = generate_pascals_triangle(6) print_triangle(pascal_triangle) ``` 这段代码展示了如何构建帕斯卡三角形，并将其格式化输出[^1]。 --- #### 动态规划的关键思路 动态规划是一种优化技术，适用于具有重叠子问题和最优子结构性质的问题。对于数字三角形问题，状态转移方程定义为： \[ dp[i][j] = \text{triangle}[i][j] + \max(dp[i+1][j], dp[i+1][j+1]) \] 其中 \( dp[i][j] \) 表示从当前位置 (\(i,j\)) 到达底部的最大路径和[^3]。 ---