注意递推,和dp的含义。这么写可以简化算法。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <climits> using namespace std; const int MAXN = 101; int matrix[MAXN][MAXN]; int dp[MAXN][MAXN]; //(i,j)到底部的最大距离 int main(){ int n; cin >> n; for(int i = 0; i < n; i++){ for(int j = 0; j <= i; j++){ scanf("%d", &matrix[i][j]); dp[i][j] = matrix[i][j]; } } for(int i = n-1; i >= 0; i--){ for(int j = 0; j <= i; j++){ dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]); } } printf("%d\n", dp[0][0]); return 0; }