最大差值数字三角形 (20分)
题目内容：
给定一个由n行数字组成的数字直角三角形,每行多一个元素：
a
b c
d e f
试设计一个算法，计算出从三角形的顶到底的一条路径，使该路径经过的数字差距最大。
计算路径时，上一行的一个元素只与下一行正下方的元素，或者其右的元素相连。如a与bc,b与de, c与ef.
最大数字差： 一个路径经过（2,1,2,3,7），则最大数字差是7-1=6
输入描述：
第1行输入行数n（n<100）
下面的n行构成数字三角形，第2行一个整数，以后每一行比上一行多一个整数。
输出描述：
最大的路径数字差.
输入样例：
5
2
1 3
2 4 5
6 3 6 8
3 7 5 4 2
输出样例
6
思路：结构体+dp
#include <iostream>
using namespace std;
typedef struct{
int mi;
int ma;
}Node;
int n;
Node a[105][105];
Node dp[105][105];
Node f(int x, int y){
if(x == n){
return dp[x][y] = a[x][y];
}
if(x < 1 || x > n || y < 1 || y > x + 1)
return a[0][0];
int d1, d2;
Node s1, s2, s;
s = a[x][y];
s1 = f(x + 1, y); s2 = f(x + 1, y + 1);
d1 = max(s1.ma, s.ma) - min(s1.mi, s.mi);
d2 = max(s2.ma, s.ma) - min(s2.mi, s.mi);
if(d1 < d2){
dp[x][y].mi = min(s2.mi, s.mi);
dp[x][y].ma = max(s2.ma, s.ma);
return dp[x][y];
}
else{
dp[x][y].mi = min(s1.mi, s.mi);
dp[x][y].ma = max(s1.ma, s.ma);
return dp[x][y];
}
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
cin >> a[i][j].mi;
a[i][j].ma = a[i][j].mi;
}
}
f(1, 1);
cout << dp[1][1].ma - dp[1][1].mi << endl;
//for(int i = 1; i <= n; i++){
// for(int j = 1; j <= i; j++){
// cout << dp[i][j].ma << " " << dp[i][j].mi << "; ";
// }
// cout << endl;
//}
return 0;
}