给定一个数字三角形，从顶部出发，在每一节点可以选择移动至左下方节点或者右下方的节点，一直走到底层要求找出一条路径使得路径上数字和最大？用线性DP写出代码

假设数字三角形的行数为 $n$，第 $i$ 行有 $i$ 个数字，用 $a_{i,j}$ 表示第 $i$ 行第 $j$ 列的数字，定义 $dp_i(j)$ 表示从数字三角形的顶部走到第 $i$ 行第 $j$ 列的最大数字和，则有状态转移方程：

$$dp_i(j)=\max\{dp_{i-1}(j),dp_{i-1}(j-1)\}+a_{i,j}$$

其中 $i\in[2,n]$，$j\in[1,i]$。

根据状态转移方程，我们可以使用一个一维数组 $dp$ 来表示状态，在更新 $dp_i(j)$ 时，只需要用 $dp_{i-1}(j)$ 和 $dp_{i-1}(j-1)$ 来更新即可。具体代码实现如下：

int n; // 数字三角形的行数
int a[N][N]; // 存储数字三角形中每个数字
int dp[N]; // 存储从顶部走到每个位置的最大数字和

int solve() {
    dp[1] = a[1][1]; // 初始化顶部的数字和
    for (int i = 2; i <= n; i++) {
        for (int j = i; j >= 1; j--) {
            dp[j] = max(dp[j], dp[j-1]) + a[i][j]; // 更新 dp[j]
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dp[i]); // 取最大值
    }
    return ans;
}

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。