当前这个点可以由它的左上方的点和正上方的点走到
dp[i][j]的含义是走到[i,j]这个点的最大值
所以状态转移方程就是 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + nums[i][j];
#include <iostream> using namespace std; const int maxn = 105; int nums[maxn][maxn]; int dp[maxn][maxn]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { cin >> nums[i][j]; } } dp[0][0] = 0; int ans = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + nums[i][j]; ans = max(ans, dp[i][j]); } } cout << ans; }