Zzz123456789101112 @ 2024-04-09 20:00:48
#include<iostream>
#include<vector>
using namespace std;
int main() {
int r,ans;
cin >> r;
vector<vector<int>> a(r+1, vector<int>(r+1, 0));
vector<vector<int>> dp(r+1, vector<int>(r+1, 0));//定义dp数组:到达(i,j)点的最大和
for(int i=1;i<=r;i++ ){
for (int j = 1; j <= i; j++)cin >> a[i][j];
}
for (int i = 1; i <= r; i++) {//遍历顺序,从上往下,从左往右//初始化,因为从(1,1)开始,所以可省略初始化
for (int j = 1; j <= i; j++) {
dp[i][j] = a[i][j]+max(dp[i - 1][j-1], dp[i - 1][j ]);
//递归,每个位置都与上一行左右两个位置的最大和有关,并比较大小
if (i == r) {
ans = max(ans, dp[i][j]);
//遍历至最后一行,在最后一行各个位置最大和取最大值
}
}
}
cout << ans;
return 0;
}
by Light_LE @ 2024-05-10 19:38:56
看样例:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
你没有考虑越界这一点:
但是你没有进行边界的特殊处理(位于边界是不能减的)
位于竖边界只考虑上边,位于斜边界只考虑左上边。其他的就把两种情况都考虑进去
希望你能 AC