注意最后条件左右移动之差不超过1,实际是一个数学问题(见注释)
#include<bits/stdc++.h>
using namespace std;
int dp[102][102],a[102][102],fl[102][102],n;
const int fu = -100;
int main() {
cin >> n;
memset(dp, fu, sizeof(dp));
for(int i=1;i<=n;i++)
for (int j = 1; j <= i; j++)
{
cin >> a[i][j];
}
dp[1][1] = a[1][1];
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
{
dp[i][j] = max(dp[i - 1][j - 1] + a[i][j], dp[i - 1][j] + a[i][j]);
}
if (n % 2 == 1)cout << dp[n][n / 2 + 1] << endl;//n是奇数时,一定会走到中间那个数
else
cout << max(dp[n][(n) / 2], dp[n][(n) / 2 + 1]);//n是偶数时,会走到中间两个数
}