動態規劃-數字三角形模型

本次分享動態規劃模型中的數字三角形模型

動態規劃做法和新就是找到狀態標識和狀態轉移方程
狀態的尋找一般從題目中獲得，每一個狀態對應陣列的一個維度
分析狀態轉移方程一般從最后一步去看，這樣比較好推出方程
所謂最后一步就是指第n-1中狀態到第n中狀態的轉移程序，推出后進而推出所有

先看引例

題目分析：
狀態表示：
從題目中獲得，最上層節點走到最下層節點的最大路徑，每一種走法所經過的每個點對應兩個狀態，x，y坐標，分析出這兩個狀態來源于如何將數字三角形存盤下來，很明顯二維矩陣，分別對應x，y坐標---->f[i][j]表示走到第i行第j列的路徑和最大值，
狀態轉移：
題目中要求路徑走法為：經過第i行第j列的元素的路徑必須經過第i-1行j列或第i-1行j-1列.
所以不難分析出狀態轉移方程f[i][j]=max(f[i-1][j],f[i-1][j-1])+w[i][j]；
代碼：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 510;
int g[N][N];
int f[N][N];
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>g[i][j];
        }
    }
    
    memset(f,-0x3f,sizeof f);
    
    f[1][1]=g[1][1];
    
    for(int i=2;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=max(f[i-1][j],f[i-1][j-1])+g[i][j];
        }
    }
    

    int res=-0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        res=max(res,f[n][i]);
    }
    cout<<res<<endl;
    return 0;
    
}

數字三角形模型是一類動態規劃問題的模型，我們下來可以看一下其他型別的題目：

例1：來源：資訊學奧賽一本通

題目分析：
狀態表示：
和數字三角形模型相同，f[i][j]表示經過第i行第j列所采摘的花生最大數量，
狀態計算：
本題目需注意走法~~~
f[i][j]=max(f[i][j],f[i-1][j]+w[i][j]);
f[i][j]=max(f[i][j],f[i][j-1]+w[i][j]);

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m,t;
int g[N][N];
int f[N][N];
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>g[i][j];
            }
        }
        memset(f,0,sizeof f);
        
        // f[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                f[i][j]=max(f[i][j],f[i-1][j]+g[i][j]);
                f[i][j]=max(f[i][j],f[i][j-1]+g[i][j]);
            }
        }
        
        cout<<f[n][m]<<endl;
    }
    
    return 0;
}

例2：來源：資訊學奧賽一本通

題目分析：
狀態表示：
與上述兩題類似 f[i][j]表示經過第i行第j列所需的最少費用
狀態計算：
f[i][j]=min(f[i][j],f[i-1][j]+g[i][j]);
f[i][j]=min(f[i][j],f[i][j-1]+g[i][j]);
f[i][j]=min(f[i][j],f[i+1][j]+g[i][j]);
f[i][j]=min(f[i][j],f[i][j+1]+g[i][j]);

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 110;
int f[N][N];
int g[N][N];
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>g[i][j];
        }
    }
    
    memset(f,0x3f,sizeof f);
    
    f[1][1]=g[1][1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=min(f[i][j],f[i-1][j]+g[i][j]);
            f[i][j]=min(f[i][j],f[i][j-1]+g[i][j]);
            f[i][j]=min(f[i][j],f[i+1][j]+g[i][j]);
            f[i][j]=min(f[i][j],f[i][j+1]+g[i][j]);
        }
    }
    
    cout<<f[n][n]<<endl;
    return 0;
    
}

例3：來源：NOIP提高組2000，洛谷

本體分析借助圖片輔助理解：

1、f[i1,j1,i2,j2]表示所有從(1,1),(1,1)分別走到(i1,j1),(i2,j2)的路徑的最大值

2、由于走兩次可以看成是兩條路徑同時走，因此k表示兩條路線當前走到的各自的橫縱坐標之和k == i1 + j1 == i2 + j2

狀態表示與狀態計算均放在上圖中
類比陣列三角形模型，不難得出f[i ][j]，但注意本題需要走兩次，等價于從起點到終點兩條完全不重復的路徑，兩條路徑就分別有兩個坐標，應該用4維陣串列示，即f[i1][j1][i2][j2]，但我們發現經過重復點等價于i1+j1==i2+j2所以我們可以引入變數k表示橫縱坐標和，這樣可以壓縮一維空間，
由于題目只能向右和向下走，且有兩條路徑，所以方案數共有2*2=4種，將其全排列即可，也可以通過二進制表示即00，01，10，11，0表示向右，1表示向下，

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 15;
int f[2*N][N][N];
int w[N][N];
int n;
int main(){
    cin>>n;
    int a,b,c;
    while(cin>>a>>b>>c,a||b||c){
        w[a][b]=c;
    }
    
    for(int k=2;k<=n+n;k++){
        for(int i1=1;i1<=n;i1++){
            for(int i2=1;i2<=n;i2++){
                int j1=k-i1;
                int j2=k-i2;
                if(j1>=1&&j1<=n&&j2<=n&&j2>=1){
                    int x=w[i1][j1];
                    if(i1!=i2){
                        x+=w[i2][j2];
                    }
                    int& t=f[k][i1][i2];
                    t=max(t,f[k-1][i1][i2]+x);
                    t=max(t,f[k-1][i1-1][i2]+x);
                    t=max(t,f[k-1][i1-1][i2-1]+x);
                    t=max(t,f[k-1][i1][i2-1]+x);
                }
            }
        }
    }
    
    cout<<f[n+n][n][n]<<endl;
    return 0;
    
}

類比題目為NOIP提高組2008 傳紙條，做法相同，不予分析

如果本文對您有幫助，記得點贊收藏哦~~，