NOIP 普及组初赛 · NOIP 2012 普及组初赛试题 第 25 题

阅读程序写结果

#include <iostream>
using namespace std;
int n,i,j,a[100][100];
int solve(int x,int y)
{
	int u,v;
	if(x==n) return a[x][y];
	u=solve(x+1,y);
	v=solve(x+1,y+1);
	if(u>v) return a[x][y]+u;
	else return a[x][y]+v;	
}
int main()
{
	cin>>n;
	for(i=1;i<=n;i++)
		for(j=1;j<=i;j++) cin>>a[i][j];
	cout<<solve(1,1)<<endl;
	return 0;	
}

输入：

5   
2   
-1 4   
2 -1 -2   
-1 6 4 0   
3 2 -1 5 8  

看到递归 max(u,v) → 数字三角形求最大路径和

易误以为需枚举所有路径；实则只需比较两子路径最大值即可

考点：递归｜数字三角形

程序在做什么

输入一个数字三角形，从顶端出发，每次可向下或向右下移动，求到达底部的最大路径和。