題目鏈接

思路（上到下）：

①從上往下遞推：

f[i][j]? = max(f[i-1][j] + g[i][j], f[i-1][j-1]+g[i][j])

②對最后一層，遍歷一下，找到最大的答案。

代碼（上到下）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1010;int n;
int g[N][N];
int f[N][N];signed main(){cin >> n;for(int i = 1; i <= n; i++){for(int j = 1;  j<=i; j++){cin >> g[i][j];}}//dpf[1][1] = g[1][1];for(int i = 2; i <= n; i++){for(int j = 1; j <= i; j++){f[i][j] = max(f[i-1][j]+g[i][j], f[i-1][j-1]+g[i][j]);}}int ans = 0;for(int i = 1; i <= n; i++){ans  = max(ans, f[n][i]);}cout << ans << endl;return 0;
}

思路（從下到上）：

①從下往上遞推：

f[i][j] = max(f[i+1][j]+g[i][j], f[i+1][j+1]+g[i][j]);

②答案就是頂點：f[1][1]

代碼（從下到上）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1010;int n;
int g[N][N];
int f[N][N];signed main(){cin >> n;for(int i = 1; i <= n; i++){for(int j = 1;  j<=i; j++){cin >> g[i][j];}}//dp 下到上for(int i = n; i >= 1; i--){for(int j = 1; j <= i; j++){f[i][j] = max(f[i+1][j]+g[i][j], f[i+1][j+1]+g[i][j]);}}cout << f[1][1] << endl;return 0;
}