自下往上做更方便 N = int(input()) # 这里我多开了一些dp的空间,这样可以简化初始化的问题 dp = [[0]*(N+1) for _ in range(N+2)] # 这里注意好坐标对应,从1开始,到N 结束 s = [[0]] for i in range(N): a = list(map(int, input().split())) s.append(a) for i in range(N, 0, -1): for j in range(i): dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])+s[i][j] print(dp[1][0]) 用c++写一遍完整版‘
时间: 2023-10-29 15:04:24 浏览: 81
当然,我会用 C++ 为您翻译并优化这段代码。给您一个提示:由于 C++ 中数组下标从 0 开始,所以在初始化时需要将 dp 数组的大小设为 (N+1) * (N+1),而 s 数组的大小需要设为 N * N。
代码如下:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1005;
int N;
int dp[MAXN][MAXN];
vector<vector<int>> s;
int main() {
cin >> N;
s.resize(N+1);
for(int i=1; i<=N; i++) {
s[i].resize(i);
for(int j=0; j<i; j++) {
cin >> s[i][j];
}
}
for(int i=N; i>=1; i--) {
for(int j=0; j<i; j++) {
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + s[i][j];
}
}
cout << dp[1][0] << endl;
return 0;
}
```
这里对代码进行了一些优化,比如使用 vector 容器来存储数据,同时将数组下标从 1 开始,使得代码更加简洁易懂。
阅读全文