DP数字三角形模型_数字三角形闫氏dp

数字三角形模板题目

数字三角形

练习题目连接

1.​​​​​​摘花生

2.最低通行费用

3.方格取数

4.传字条

 数字三角形模型解题思路

根据闫氏DP分析法可以得出

根据不同的属性得到状态转移方程即可

习题代码

1.摘花生

状态转移方程f[i,j]=max(f[i-1][j]+w[i][j],f[i-1][j]+w[i][j];

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int w[N][N];
int f[N][N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof f);
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&w[i][j]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                f[i][j]=max(f[i-1][j]+w[i][j],f[i][j-1]+w[i][j]);
        printf("%d\n",f[n][m]);
    }
    return 0;
}

2.通行费用

这题多了一个数学背景商人必须在2*n-1的时间完成行走，意味着他是不可以走回头路的，得到性质以后就是摘花生问题的变形

状态转移方程同摘花生 但是变为求min

由于是求最小值，所以边界会有一些特判

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int f[N][N];
int w[N][N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&w[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i==1&&j==1) f[i][j]=w[i][j];
            else
            {
                f[i][j]=0x3f3f3f3f;
                ///特判第一行和第一列
                if(i>1) f[i][j]=min(f[i][j],f[i-1][j]+w[i][j]);
                if(j>1) f[i][j]=min(f[i][j],f[i][j-1]+w[i][j]);
            }
        }
    printf("%d\n",f[n][n]);
    return 0;
}

3.放格取数

同样是变形 是同时去走两条不同路

状态方程变为f[i1,j1,i1,j2] 四维太多考虑优化

因为只有i1+j1=i2+j2相同时，两个点才会有可能重合 所以可以设k=i1+j1=i2+j2

则方程可以优化为f[k,i1,i2]表示从起点开始分别走到（i1,k-i1）和（i2,k-i2）的路线

特判只有i1=i2时，路线才会相同（走过的点收益清零）

状态转移方程看代码

#include <bits/stdc++.h>
using namespace std;
const int N=12;
int f[N+N][N][N];
int w[N][N];
int n;
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(f,0,sizeof f);
        memset(w,0,sizeof w);
        int a,b,c;
        while(scanf("%d%d%d",&a,&b,&c))
        {
            if((!a)&&(!b)&&(!c))
            {
                break;
            }
            w[a][b]=c;
        }
        for(int k=2;k<=n+n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                {
                    int l=k-i,m=k-j;
                    if(l>=1&&l<=n&&m>=1&&m<=n)///判断合法范围
                    {
                        int t=w[i][k-i];
                        if(i!=j) t+=w[j][k-j];///路径相同有一次的点收益为0
                        ///状态转移方程
                        f[k][i][j]=max(f[k][i][j],f[k-1][i-1][j-1]+t);
                        f[k][i][j]=max(f[k][i][j],f[k-1][i-1][j]+t);
                        f[k][i][j]=max(f[k][i][j],f[k-1][i][j-1]+t);
                        f[k][i][j]=max(f[k][i][j],f[k-1][i][j]+t);
                    }
                }
        printf("%d\n",f[n+n][n][n]);
    }
    return 0;
}

4.传纸条

与3一样

#include <bits/stdc++.h>
using namespace std;
const int N=55;
int n,m;
int f[N+N][N][N];
int w[N][N];
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(f,0,sizeof f);
        memset(w,0,sizeof w);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&w[i][j]);
        for(int k=2;k<=n+m;k++)
            for(int i1=1;i1<=n;i1++)
                for(int i2=1;i2<=n;i2++)
                {
                    int j1=k-i1,j2=k-i2;
                    if(j1>=1&&j1<=m&&j2>=1&&j2<=m)
                    {
                        int t=w[i1][j1];
                        if(i1!=i2) t+=w[i2][j2];
                        f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1-1][i2-1]+t);
                        f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1][i2-1]+t);
                        f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1-1][i2]+t);
                        f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1][i2]+t);
                    }
                }
                printf("%d\n",f[n+m][n][n]);
    }
    return 0;
}