关于这题 最 最 最详细的题解

这题我们考虑用DP(动态规划）

知识点：
二维网格上的路径最值问题、DP 的经典问题——数字三角形

思路：

dp[i][j]：从起点（左上角）走到第 i 行第 j 列的最大数字之和

状态转移：

可以上面 (i - 1, j) 或左边 (i, j - 1) 走到 (i, j)，从两个选择中决策取最大值，再加上 (i, j) 位置上的值。
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][j]

边界：

数据是个三角形，第 i 行只有 i 列，满足 j <= i 的位置 (i, j) 才是合法位置。
可将不合法位置作为边界，不合法位置取不到数字（数字之和为 0） 。即对于所有的 j > i，dp[i][j] = 0。

AC代码如下：

#include<bits/stdc++.h>
using namespace std; 
using ll=long long;
const int N=1005;
int n,dp[N][N],a[N][N],i,j;//从起点(1,1)走到(i,j)能获得的最大组数和
int main(){
	cin>>n;
	for(i=1;i<=n;i++){
		for(j=1;j<=i;j++)
		cin>>a[i][j];
	}
	dp[1][1]=a[1][1];
	for(i=2;i<=n;i++){
		for(j=1;j<=i;j++){
			dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][j];
		}
	}
	int ans=0;
	for(i=1;i<=n;i++)
		ans=max(ans,dp[n][i]);
	cout<<ans<<endl;
	return 0;
}