问题描述

2017-10-04 09-11-31 创建的截图.png 2017-10-04 09-17-03 创建的截图.png

解题思路

2017-10-04 09-17-12 创建的截图.png

递归程序实现

#include<iostream>
using namespace std;

const int MAXN=100;
int d[MAXN+1][MAXN+1];
int n;

int maxSum(int i,int j)
    {
    if(i==n) return d[n][j];
    else
            {
            return max(maxSum(i+1,j),maxSum(i+1,j+1))+d[i][j];
            }
    }

int main()
    {
    cin>>n;
    for(int i=1; i<n+1; i++)
        for(int j=1; j<i+1; j++)
            cin>>d[i][j];

    cout<<maxSum(1,1)<<endl;
    }

运行结果

2017-10-04 09-34-06 创建的截图.png

当n数目变大时，程序运行时容易超时!

为什么超时?

2017-10-04 09-37-16 创建的截图.png

如果采用递归的方法，深度遍历每条路径，存在大量重复计算则时间复杂度为2的n次方，对于 n = 100时，肯定超时。

改进

2017-10-04 09-40-38 创建的截图.png

记忆递归型动规程序实现

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN=100;
int d[MAXN+1][MAXN+1];
int maxSum[MAXN+1][MAXN+1];
int n;

int MaxSum(int i,int j)
    {
    if(maxSum[i][j]!=-1) return maxSum[i][j];
    if(i==n) {
            maxSum[n][j]=d[n][j];
            }
    else {
            maxSum[i][j]=max(MaxSum(i+1,j),MaxSum(i+1,j+1))+d[i][j];
            }
    return maxSum[i][j];
    }

int main()
    {
    cin>>n;
    for(int i=1; i<n+1; i++)
        for(int j=1; j<i+1; j++)
            cin>>d[i][j];
    memset(maxSum,-1,sizeof(maxSum));
    cout<<MaxSum(1,1)<<endl;
    }

运行结果

2017-10-04 09-49-31 创建的截图.png

递归转递推

递归:函数调用，存在时间开销；递归次数多，栈可能会爆掉；不用递归，更快，更节省空间

2017-10-04 09-51-14 创建的截图.png 2017-10-04 09-51-21 创建的截图.png 2017-10-04 09-51-23 创建的截图.png 2017-10-04 09-51-26 创建的截图.png 2017-10-04 09-51-28 创建的截图.png

......

2017-10-04 09-51-37 创建的截图.png

"人人为我"递推型动规程序实现

#include<iostream>
using namespace std;

const int MAXN=100;
int d[MAXN+1][MAXN+1];
int maxSum[MAXN+1][MAXN+1];
int n;


int main()
    {
    cin>>n;
    for(int i=1; i<n+1; i++)
        for(int j=1; j<i+1; j++)
            cin>>d[i][j];
    for(int i=1;i<n+1;i++)
        maxSum[n][i]=d[n][i];
    for(int i=n-1;i>0;i--)
        for(int j=1;j<i+1;j++)
            maxSum[i][j]=max(maxSum[i+1][j],maxSum[i+1][j+1])+d[i][j];
    cout<<maxSum[1][1]<<endl;
    }

运行结果

2017-10-04 10-02-16 创建的截图.png

空间优化

没必要用二维maxSum数组存储每一个MaxSum(r,j)，只要从底层一行行向上递推，那么只要一维数组maxSum[100] (滚动数组) 即可，即只要存储一行的MaxSum值就可以了

进一步考虑，连maxSum数组都可以不要，直接用D的第n行替代maxSum即可。节省空间，时间复杂度不变

空间优化程序实现

#include<iostream>
using namespace std;

const int MAXN=100;
int* maxSum;
int d[MAXN+1][MAXN+1];
int n;


int main()
    {
    cin>>n;
    for(int i=1; i<n+1; i++)
        for(int j=1; j<i+1; j++)
            cin>>d[i][j];
    maxSum=d[n];
    for(int i=n-1;i>0;i--)
        for(int j=1;j<i+1;j++)
            maxSum[j]=max(maxSum[j],maxSum[j+1])+d[i][j];
    cout<<maxSum[1]<<endl;
    }

运行结果

2017-10-04 10-09-11 创建的截图.png