线性动态规划-数字金字塔

动态规划(Dynamic Programming, DP)是对一类最优化问题的解决方法。

数字金字塔：观察下面的数字多字塔，写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大，每一步可以从当前点走到左下方的点，也可以到达右下方的点。

方法1：遍历搜索
此方法就是把所有可能性都搜索，然后比较大小。算法复杂度O(2^N)

/**************************************************************** 
 * Description: C++ implementation of Maximum path sum in a triangle.
 * Author: Alex Li
 * Date: 2023-06-14 19:51:06
 * LastEditTime: 2023-06-14 20:51:32
****************************************************************/
#include <iostream>
using namespace std;
const int MAXN=1005;
int NT[MAXN][MAXN];  // use a array to store the Number Triangle.
int N;   // N is max level of the number triangles
int MaxSum; //  the final Maximum path sum.

void Dfs(int x,int y, int Current){
   if(x==N){
       if(Current>MaxSum)
       MaxSum=Current;
       return;
   }
   Dfs(x+1,y,Current+NT[x+1][y]);
   Dfs(x+1,y+1,Current+NT[x+1][y+1]);
}
int main(){
    cin>>N;
    for (int i = 1; i <=N; i++){
        for (int j = 1; j <=i;j++){
            cin>>NT[i][j];
        }
    }
        MaxSum=0;
        Dfs(1,1,NT[1][1]);
        cout<<MaxSum<<endl;
        return 0;
}

方法2：记忆搜索。
建立新的数组]Sum[][]，记录从底向上每一层的最优路径。时间复杂度O(n^2)

/**************************************************************** 
 * Description: C++ implementation of Maximum path sum in a triangle.
 * Author: Alex Li
 * Date: 2023-06-14 19:51:06
 * LastEditTime: 2023-06-14 22:32:27
****************************************************************/
#include <iostream>
using namespace std;
const int MAXN=1005;
int NT[MAXN][MAXN];  // use a array to store the Number Triangle.
int Sum[MAXN][MAXN];   //  store the max sum of path 
int N;   // N is max level of the number triangles

// from bottom to top
int  DFS(int x,int y){
   if(Sum[x][y]==-1){  // if Sum[][] doesn't calculate.
       if(x==N)Sum[x][y]=NT[x][y];
       else Sum[x][y]=NT[x][y]+max(DFS(x+1,y),DFS(x+1,y+1));
       
   }
  return Sum[x][y];
}
int main(){
    cin>>N;
    for (int i = 1; i <=N; i++){
        for (int j = 1; j <=i;j++){
            cin>>NT[i][j];
        }
    }

     for (int i = 1; i <=N; i++){
        for (int j = 1; j <=i;j++){
            Sum[i][j]=-1;
        }
    }
        DFS(1,1);
        cout<<Sum[1][1]<<endl;
        return 0;
}

方法3：动态规划
用Sum[][]数组记录从上到下，每一步的最优解。O(n^2)

/**************************************************************** 
 * Description: C++ implementation of Maximum path sum in a triangle.
 * Author: Alex Li
 * Date: 2023-06-14 19:51:06
 * LastEditTime: 2023-06-14 22:38:23
****************************************************************/
#include <iostream>
using namespace std;
const int MAXN=1005;
int NT[MAXN][MAXN];  // use a array to store the Number Triangle.
int Sum[MAXN][MAXN];   //  store the max sum of path 
int N;   // N is max level of the number triangles

//from top to bottom
int main(){
    cin>>N;
    for (int i = 1; i <=N; i++){
        for (int j = 1; j <=i;j++){
            cin>>NT[i][j];
        }
    }
    Sum[1][1]=NT[1][1];
    for (int i = 2; i <=N; i++){
        for (int j = 1; j <= i; j++)
        Sum[i][j]=max(Sum[i-1][j-1],Sum[i-1][j])+NT[i][j];
        }
    int ans=0;

    for(int j=1;j<=N;j++)
         ans=max(ans,Sum[N][j]);
    cout<<ans<<endl;
        return 0;
}

洛谷：P1216

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

线性动态规划-数字金字塔