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  
```

阅读程序写结果

答案

14

题解

考点定位

数字三角形的最大路径和。

解题过程

solve(x,y) 返回从 (x,y) 到底层的最大路径和，每步只能走到下一行同列或右侧相邻列。

自底向上计算“当前数+两个后继的较大值”：

第二行第二项为 4+max(8,7)=12；顶点为 2+max(9,12)=14。一条最优路径是 2→4→−1→4→5，总和为 14。

答案：14。

易错提醒

每次只能比较相邻的两个后继。4+8=12，不能误算为 11；原卷与程序在本题没有答案冲突。