#include <iostream> #include <vector> using namespace std; int solve(int n, vector<vector<int>>& a, int i, int j) { if (i == n) { return 0; } else { return a[i][j] + max(solve(n, a, i + 1, j), solve(n, a, i + 1, j + 1)); } } int main() { int n; cin >> n; vector<vector<int>> a(n, vector<int>(n)); for (int i = 0; i < n; i++) for (int j = 0; j <= i; j++) cin >> a[i][j]; cout << solve(n, a, 0, 0) << endl; return 0; } 优化这段代码。

好的，我来为你优化这段代码。优化的思路是使用动态规划来避免重复计算子问题。

优化后的代码如下：

#include <iostream>
#include <vector>
using namespace std;

int solve(int n, vector<vector<int>>& a) {
    vector<vector<int>> dp(n, vector<int>(n));
    // 初始化最后一行的值
    for (int j = 0; j < n; j++) {
        dp[n-1][j] = a[n-1][j];
    }
    // 从倒数第二行开始逐行计算最优解
    for (int i = n-2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
        }
    }
    return dp[0][0];
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            cin >> a[i][j];
    cout << solve(n, a) << endl;
    return 0;
}

这样，我们通过使用动态规划来保存子问题的最优解，避免了重复计算，从而提高了代码的效率。