数字三角形(POJ1163)
在上面的数字三角形中寻找一条从顶部到底边的路径，使得
路径上所经过的数字之和最大。路径上的每一步都只能往左下或
右下走。只需要求出这个最大和即可，不必给出具体路径。
三角形的行数大于1小于等于100，数字为 0 - 99
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
解题思路：
用二维数组存放数字三角形。
D( r, j) : 第r行第 j 个数字(r,j从1开始算)
MaxSum(r, j) : 从D(r,j)到底边的各条路径中，
最佳路径的数字之和。
问题：求 MaxSum(1,1)
典型的递归问题。
D(r, j)出发，下一步只能走D(r+1,j)或者D(r+1, j+1)。故对于N行的三角形：
if ( r == N)
MaxSum(r,j) = D(r,j)
else
MaxSum( r, j) = Max{ MaxSum(r＋1,j), MaxSum(r+1,j+1) } + D(r,j)。、
#include<stdio.h> #include<algorithm> using namespace std; int n; int a[101][101]; int m[101][101]; int maxsum(int i,int j) { if(m[i][j]!=-1) { return m[i][j]; } if(n==i) { return a[i][j]; } int x=maxsum(i+1,j); int y=maxsum(i+1,j+1); return m[i][j]=max(x,y)+a[i][j]; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { scanf("%d",&a[i][j]); m[i][j]=-1; } } printf("%d",maxsum(1,1)); return 0; }
