动态规划实现数字三角形

动态规划是一种解决优化问题的算法思想，通常用于求解具有重叠子问题和最优子结构的问题，比如计算斐波那契数列、背包问题等。在处理数字三角形问题时，动态规划可以用来高效地找出从顶点到任意一点的最大路径和。

假设我们有一个数字组成的三角形数组，比如：

1
2 3
4 5 6
7 8 9 10

动态规划的步骤如下：

1. 初始化：给每个三角形的第一行和第一列赋值为该行或列的第一个元素作为基础情况。
对于这个例子，初始状态会是 `dp[0][0] = triangle[0][0]` 和 `dp[0][i] = triangle[0][i]`（对于所有 i），以及 `dp[i][0] = triangle[i][0]`（对于所有 i）。

2. 状态转移方程：对于每个内部节点 `(i, j)`，其值等于左上角节点 `(i-1, j-1)` 的值加上当前节点的值。即 `dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]`。

3. 计算过程：从第二行开始，向上逐层计算每个节点的值，直到到达顶部。

4. 返回结果：最终的 `dp[n-1][n-1]` 就是整个三角形的最大路径和，其中 `n` 是三角形的行数。