动态规划2---例9.2数字金字塔

野性酷女 2023-07-11 11:27 28阅读 0赞

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

方法一:
    从最高点按照规则走到最低点的路径的最大的权值和，路径起点终点固定，走法规则明确，可以考虑用搜索算法
    定义递归函数 void Dfs（int x,int y, int Curr），其中x,y表示当前已从（1,1）走到（x,y),目前已走路径上的权值和为Cur
    当x=N时，到达递归出口，如果Cur比Ans大，则把Ans更新为Cur；
    否则向下一行两个位置行走，即递归执行Ds（x+1，y,Cur+A[x+1][y]）和Dfs（x+1，y+1，Cur+A[x+1][y+1]）
    #include <iostream>
    #include<bits/stdc++.h>
    using namespace std;
    
    const int MAXN=1005;
    int A[MAXN][MAXN],F[MAXN][MAXN],N,Ans;
    
     //递归函数
    void Dfs(int x,int y,int Cur){
        //递归的结束条件
        //查询到最后一行
        if(x==N){
            //如果当前路径和大于之前的
            if(Cur>Ans){
    
                Ans=Cur;
            }
            return ;
        }
    
        //向下一行两个位置行走
        Dfs(x+1,y,Cur+A[x+1][y]);
        Dfs(x+1,y+1,Cur+A[x+1][y+1]);
    }
    
     //主函数
    int main(){
        //数据初始化
        //输入行数和数字
        cin>>N;
        for (int i = 1; i <=N ; ++i) {
            for (int j = 1; j <=i ; ++j) {
                cin>>A[i][j];
            }
        }
        //初始化长度
        Ans=0;
    
        //调用递归函数
        Dfs(1,1,A[1][1]);
    
        //打印输出答案
        cout<<Ans<<endl;
    
        return 0;
    }
    
    
    方法二：
    方法一之所以会超时，是因为进行了重复搜索
    记忆化搜索需要对方法一中的搜索进行改装。由于需要记录从一个点开始到终点的路径的最大权值和，因此我们重新定义递归函数Dfs
    ①第一步向左：那么从（x,y）出发到终点的这类路径就被分成两个部分，先从（x,y）到（x+1，y）再从（x+1，y）到终点，
     第一部分固定权值就是A[x][y]，要使得这种情况的路径权值和最大，那么第二部分从（x+1，y）到终点的路径的权值和也要最大，
     这一部分与前面的Dfs（x,y）的定义十分相似，仅仅是参数不同，因此这一部分可以表示成Dfs（x+1，y）。
     综上，第一步向左的路径的最大权值和为A[x][y]+Dfs(x+1,y)
    ②第一步向右：这类路径要求先从（x,y）到（x+1，y+1）再从（x+1.y+1）到终点，
     分析方法与上面一样，这类路径最大权值和为A[x][y]+Dfs（x+1，y+1）；
     为了避免重复搜索，我们开设全局数组F[x][y]记录从（x,y）出发到终点路径的最大权值和，
     一开始全部初始化为-1表示未被计算过。在计算Dfs（x,y）时，首先查询F[x][y]，
     如果F[x][y]不等于-1，说明Ds（x,y）之前已经被计算过，直接返回F[x][y]即可，
     否则计算出Dfs（x,y）的值并存储在F[x][y]中。
    #include<iostream>
    #include <cstring>
    
    using namespace std;
    const int MAXN=505;
    int A[MAXN][MAXN],F[MAXN][MAXN],N;
    
     //递归函数
    int Dfs(int x,int y){
        //先判断是否可行
        if(F[x][y]==-1){
            if(x==N){
                F[x][y]=A[x][y];
            }else{
                F[x][y]=A[x][y]+max(Dfs(x+1,y),Dfs(x+1,y+1));
            }
        }
    
        return F[x][y];
    }
    
     //主函数
    int main(){
        //数据初始化
        cin>>N;
        for (int i = 1; i <=N ; ++i) {
            for (int j = 1; j <=i ; ++j) {
                cin>>A[i][j];
            }
        }
        memset(F,-1, sizeof(F));
    
        //调用函数
        Dfs(1,1);
    
    
        //输出数据
        cout<<F[1][1]<<endl;
    
        return 0;
    }
    
    
    方法三：
    动态规划（顺推法）：
    上面方法二的记忆搜索本质上已经是动态规划了
    ①确定状态：
    题目要求从（1,1）出发到最底层路径最大权值和，路径中是各个点串联而成，路径起点固定，终点和中间点相对不固定。
     因此定义F[x][y]表示从（1,1）出发到达（x,y）的路径最大权值和。
     最终答案Ans=max{F[N][1]，F[N][2]，...F[N][N]}
    ②确定状态转移方程和边界条件：
    不去考虑（1,1）到（x,y）的每一步是如何走的考虑最后一步是如何，根据最后一步是向左还是向右分成以下两种情况：
    向左：最后一步是从（x-1，y）走到（x,y），此类路径被分割成两部分，
     第一部分是从（1,1）走到（x-1，y），第二部分是从（x-1，y）走到（x,y），
     要计算此类路径的最大权值和，必须用到第一部分的最大权值和，
     此部分问题的性质与F【x】【y】的定义一样，就是F【x-1， y】，第二部分就是 A【x】【Y】，
     两部分相加即得到此类路径的最大权值和为F【x-1，y】+A【x】【y】；
    向右：最后一步是从（x-1，y-1）走到（x,y），此类路径被分割成两部分，
     第一部分是从（1,1）走到（x-1，y），第二部分是从（x-1，y）走到（x,y），
     分析方法如上。此类路径的最大权值和为F【x-1，y-1】+A【x,y】； F【x】【y】的计算需要求出上面两种情况的最大值。
     综上，得到状态转移方程如下：
    F【x】【y】=max{ F【x-1，y-1】，F【x-1】【y】}+A【x,y】
    与递归关系式还需要递归终止条件一样，这里我们需要对边界进行处理，以防无限递归下去。
     观察发现计算F【x】【y】时需要用到F【x-1】【y-1】和F【x-1，y】，是上一行的元素
     ，随着递归的深入，最终都要用到第一行的元素F【1】【1】，F【1】【1】的计算不能再使用状态转移方程来求，
     而是应该直接赋予一个特值A【1】【1】。这就是边界条件。
    ③程序实现：
    由于状态转移方程就是递归关系式，边界条件就是递归终止条件，
     所以可以用递归来完成，递归存在重复调用，利用记忆化可以解决重复调用的问题，方法二已经讲过。
     记忆化实现比较简单，而且不会计算无用状态，但递归也会受到“栈的大小”和“递推十回归执行方式”的约束，
     另外记忆化实现调用状态的顺序是按照实际需求而展开，没有大局规划，不利于进一步优化。
    这里使用一种迭代的方法
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    const int MAXN=1005;
    int A[MAXN][MAXN],F[MAXN][MAXN],N;
    
    int main(){
        //初始化数据
        cin>>N;
        for (int i = 1; i <=N ; ++i) {
            for (int j = 1; j <=i ; ++j) {
                cin>>A[i][j];
            }
        }
        F[1][1]=A[1][1];
    
        //使用迭代法处理
        for (int i = 2; i <=N ; ++i) {
            for (int j = 1; j <=i ; ++j) {
                //所在点的值=上一步max{右半部,左半部}+上一步到这一步的值
                F[i][j]=max(F[i-1][j-1],F[i-1][j])+A[i][j];
            }
        }
        int ans=0;
        for (int i = 1; i <=N ; ++i) {
            ans=max(ans,F[N][i]);
        }
    
        //输出结果
        cout<<ans<<endl;
    
        return 0;
    }
    
    //方法四：
    //动态规划（逆推法）：
    //此题如果用贪心算法得不到最优解（因为贪心算法要求每一步得到的数最大，但是最后的和不是最大，贪心的问题：目光短浅）
    //动态规划求解：过程归纳为：自顶向下分析，自底向上计算
    //基本方法：
    //划分阶段：按三角形的行划分阶段，若有n行，则有n-1个阶段。
    //A.从根结点13出发，选取它的两个方向中的一条支路，当到倒数第二层时，每个结点其继仅有两个结点，可以直接比较，选择最大值为前进方向，从而求得从根结点开始到底端的最大路径。
    //B.自底向上计算：（给出递推式和终止条件）
    //①从底层开始，本身数即为最大数；
    //②倒数第二层的计算，取决于底层的数据。以此类推
    //C.使用直角三角形便于搜索，使用三维数组表示数塔
    #include <iostream>
    #include <cstring>
    using namespace std;
    
    //主函数
    int main(){
        //数据初始化
        int n,x,y;
        int a[51][51][4];
        //输入行数
        cin>>n;
        //输入数据
        memset(a,0, sizeof(a));
        for (x = 1; x<=n ; ++x) {
            for (y= 1; y<=x ; ++y) {
                cin>>a[x][y][1];
                a[x][y][2]=a[x][y][1];
                a[x][y][3]=0;
            }
        }
    
        for (int x = n-1; x>=1 ; x--) {
            for (int y = 1; y <=x ; ++y) {
                //选择路径，保留最大路径值
                if(a[x+1][y][2]>a[x+1][y+1][2]){
                    a[x][y][2]=a[x][y][2]+a[x+1][y][2];
                    a[x][y][3]=0;
                }else{
                    a[x][y][2]=a[x][y][2]+a[x+1][y+1][2];
                    a[x][y][3]=1;
                }
    
            }
        }
    
        cout<<a[1][1][2]<<endl;
    
        y=1;
        //输出数塔值的路径
        for (int x = 1; x <=n-1 ; ++x) {
            cout<<a[x][y][1]<<"->";
            y=y+a[x][y][3];
        }
        cout<<a[n][y][1]<<endl;
    
        return 0;
    }