递归，递推，记忆化搜索，空间优化（数字三角形）-白红宇

递归，递推，记忆化搜索，空间优化（数字三角形）

阅读量：7058 次

发布时间：2019-06-28

本文共 2292 字，大约阅读时间需要 7 分钟。

题目链接：

1、递归思想：第一层到最底层的最优路径可以分解为：第一层到第二层来，再加上第二层的最优路径

状态:

#include 
     
      #include 
      
       #define MAX 101using namespace std;int maps[MAX][MAX];int n;int Sum(int i,int j){    if(i==n)        return maps[i][j];    else return max(Sum(i+1,j),Sum(i+1,j+1))+maps[i][j];}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        for(int j=1;j<=i;j++)        {            scanf("%d",&maps[i][j]);        }    }    printf("%d\n",Sum(1,1));    return 0;}

2、通过记录表记录每一个点的最优解，从而避免重复计算。

Memory: 332KTime: 0MSLanguage: C++Result: Accepted

#include 
     
      #include 
      
       using namespace std;const int maxn=105;int n;int maps[maxn][maxn];int maxsum[maxn][maxn];int Maxsum(int i,int j){    int x,y;    if(maxsum[i][j]!=-1)        return maxsum[i][j];    if(i==n)        return maps[i][j];    x=Maxsum(i+1,j);    y=Maxsum(i+1,j+1);    maxsum[i][j]=max(x,y)+maps[i][j];    return maxsum[i][j];}int main(){    cin>>n;    for(int i=1;i<=n;i++)    {        for(int j=1;j<=i;j++)        {            cin>>maps[i][j];            maxsum[i][j]=-1;        }    }    cout<
       
        <

3、递归变递推

Memory: 332KTime: 0MSLanguage: C++Result: Accepted

#include 
     
      #include 
      
       using namespace std;const int maxn=105;int n;int maps[maxn][maxn];int maxsum[maxn][maxn];int main(){    cin>>n;    for(int i=1;i<=n;i++)    {        for(int j=1;j<=i;j++)        {            cin>>maps[i][j];        }    }    for(int i=1;i<=n;i++)        maxsum[n][i]=maps[n][i];    for(int i=n-1;i>=1;i--)    {        for(int j=1;j<=i;j++)        {            maxsum[i][j]=max(maxsum[i+1][j],maxsum[i+1][j+1])+maps[i][j];        }    }    cout<
       
        <

4、空间优化，不需要用到二维记录表。

Memory: 204KTime: 0MSLanguage: C++Result: Accepted

#include 
     
      #include 
      
       #define MAX 101using namespace std;int maps[MAX][MAX];int sum[MAX];int main(){     int n;     scanf("%d",&n);     for(int i=1;i<=n;i++)     {         for(int j=1;j<=i;j++)            scanf("%d",&maps[i][j]);     }     for(int i=1;i<=n;i++)        sum[i]=maps[n][i];     for(int i=n-1;i>=1;i--)     {         for(int j=1;j<=i;j++)            sum[j]=max(sum[j],sum[j+1])+maps[i][j];     }     printf("%d\n",sum[1]);}