试题链接：

1.记忆递归型（自顶向下）

D[i][j]来存数字

典型的递归问题：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)用ans[i][j]来存计算出的结果，避免重复计算

#include 
    
     using namespace std;#define MAX 101int D[MAX][MAX];int ans[MAX][MAX];int n;int MaxSum(int i,int j){    if(ans[i][j]!=-1)        return ans[i][j];    if(i==n)        ans[i][j]=D[i][j];    else        ans[i][j]=max(MaxSum(i+1,j),MaxSum(i+1,j+1))+D[i][j];    return ans[i][j];}int main(){    cin>>n;    for(int i=1; i<=n; i++)    {        for(int j=1; j<=i; j++)        {            cin>>D[i][j];            ans[i][j]=-1;        }    }    cout<
    

2.循环递推法（自底向上）

#include 
    
     using namespace std;#define MAX 101int D[MAX][MAX];int ans[MAX][MAX];int n;int main(){    cin>>n;    for(int i=1; i<=n; i++)  //读入数字        for(int j=1; j<=i; j++)            cin>>D[i][j];    for(int j=1; j<=n; j++)  //先初始化最后一行        ans[n][j]=D[n][j];            for(int i=n-1; i>=1; i--)    {        for(int j=1; j<=n; j++)            ans[i][j]=max(ans[i+1][j],ans[i+1][j+1])+D[i][j];    }    cout<
     
      <
     
    

空间优化

#include 
    
     using namespace std;#define MAX 101int D[MAX][MAX];int *ans;int n;int main(){    cin>>n;    for(int i=1; i<=n; i++)  //读入数字        for(int j=1; j<=i; j++)            cin>>D[i][j];    ans=D[n]; //ans指向第n行    for(int i=n-1; i>=1; i--)        for(int j=1; j<=i; j++)            ans[j]=max(ans[j],ans[j+1])+D[i][j];    cout<
     
      <