递归方法解决数塔问题

状态转移方程：

d[i][j]=a[i][j]+max{d[i+1][j],d[i+1][j+1]}

注意：1\d[i][j]表示从i,j出发的最大总和;

2\变界值设为0;3\递归变界为n;

4\结果为d[1][1]

#include
      
       #include
       
        using namespace std;#define maxn 1000+5int n;int a[maxn][maxn];int d[maxn][maxn];int D(int i,int j){             //递归解决状转移方程    return a[i][j]+(i==n ? 0:max(D(i+1,j),D(i+1,j+1)));}int main(){        for(;cin>>n && n;){        //输入及d的初始化        memset(d,0,sizeof(d));        int i,j;        for(i=1;i<=n;i++){            for(j=1;j<=i;j++){                cin>>a[i][j];            }        }        for(i=1;i<=n;i++){    //求d[][]            for(j=1;j<=i;j++){                d[i][j]=D(i,j);            }        }        cout<
        
         <<'\n';  //输出    }}