A22681.数字三角形 题解

这题是一道经典的动态规划（dp）。它要算的是和，所以这题有两个方法。

第一个正推
正推顾名思义就是从上往下dp，
每次在下方或右下方选一个最大的数，然后加上它，并继续dp。
以下是正推代码

#include<bits/stdc++.h>
using namespace std;
int dp[1002][1002];
int a[1002][1002];
int r,maxx;
int main(){
	cin>>r;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=i;j++){
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];//正下方和右下方
		}
	}
	for(int i=1;i<=r;i++){
		maxx=max(maxx,dp[r][i]);//因为是正推，所以最底下一排要比较
	}
	cout<<maxx;
	return 0;
}

第二个逆推

逆推顾名思义就是从下往上dp，
每次在上方或左上方选一个最大的数，然后加上它，并继续dp。
以下是逆推代码

#include<bits/stdc++.h>
using namespace std;
int a[1002][1002];
int dp[1002][1002];
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
		}
	}
	for(int i=n;i>=1;i--){//逆推从n开始
		for(int j=1;j<=i;j++){
			dp[i][j]=max(dp[i+1][j+1],dp[i+1][j])+a[i][j];//这里要加上原数
		}
	}
	cout<<dp[1][1];//逆推就是最顶上的数，所以无需比较
	return 0;
}

这只是我的一些方法，请大佬多关照。