DP模板-贪心优化求较大

#include<iostream>
using namespace std;
const int N = 101;
int a[N][N];//记录数塔 
int dp[N][N]; //记录到达i, j值所需要的最大路径和 
int main(){
	int n;
	cin>>n;
	//输入数塔信息 
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			cin>>a[i][j]; 
		}
	}
	//处理一个状态：最后一行的dp有值吗？     是有的，为数塔的最后底层 
	for(int j=0;j<n;j++){
		dp[n-1][j] = a[n-1][j];//初始化了最后一行的状态 
	} 
	//开始dp！！！从倒数第二层往上处理！ 
	for(int i=n-2;i>=0;i--){
		for(int j=0;j<=i;j++){
			//每个位置的最大路径和是等于 当前点的值 + 右下和左下的较大值
			dp[i][j] = a[i][j] + max(dp[i+1][j],dp[i+1][j+1]);  
		}
	} 
	cout<<dp[0][0]<<endl;//输入顶部的最大路径和！ 
	//先dp子问题，从倒数 
	return 0;
}