数字三角形模型

数字三角形是动态规划中的一种模型，主要用于从一个图的左上角，每次移动只有两个方向，移动到右下角，移动过程中路径上的一些特性，或者再抽象一点，每一步只有两种被更新的方式（对应下移和右移两个操作），求完成操作过程中的一些特性。

模型：

898. 数字三角形(活动 - AcWing)

从顶端向下，每次只能向左下或者向右下，要求出到底端路径和的最大值。

思路：这个图虽然是这么画，但是我们用一个二维数组去存的时候实际是按如下格式存的：

7?

3 8

8 1 0

2 7 4 4

4 5 2 6 5

很容易发现，每个点只可能从它正上方或者左上方更新而来，那么就符合数字三角形的模型，每一步只有两个状态来更新它。那么我们按照动态规划的思路来分析：

状态表示：定义f[i][j]表示从顶点到[i,j]的路径和的集合，f[i][j]的值表示这些路径和中的最大值。

状态计算：那么就是状态划分，划分的依据是倒数第二步从何而来，有两个方向，

一个是正上方：dp[i][j]=dp[i-1][j]+w[i][j]

一个是左上方：dp[i][j]=dp[i-1][j-1]+w[i][j]

这道题差不多就出来了，但是还有一个很关键的地方就是临界值的处理，对于第一列的数据和每行最后一个数据，它们的状态很显然只有一种更新方式，加个特判即可。

至于结果，我们需要的是到最后一行的最大值，没说是到哪个点，所以我们直接遍历dp[][]的最后一行即可，因为dp[i][j]存的就是到[i,j]的最大值。

#include<bits/stdc++.h>
using namespace std;
int f[600][600],w[600][600];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++) 
            scanf("%d",&w[i][j]);  
    f[1][1]=w[1][1];
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if(j==1) f[i][j]=f[i-1][j]+w[i][j];
            else if(j==i) f[i][j]=f[i-1][j-1]+w[i][j];
            else f[i][j]=max(f[i-1][j],f[i-1][j-1])+w[i][j];
        }
    }
    int mx=-5000000;
    for(int i=1;i<=n;i++) mx=max(mx,f[n][i]);
    cout<<mx;
}

应用

?1015. 摘花生（1015. 摘花生 - AcWing题库）

题目大意：

从左上到右下，每次只能向右走或者向下走，节点上有一些花生，问最多能摘到多少个花生。

思路：这题的图虽然不是三角形，但显然，每次的点只有两个移动方向，也即每个点的状态只可能由两种状态转移而来，所以实际上也是数字三角形的模型。我们按照数字三角形的模板进行分析：

首先是状态表示，定义一个二维数组dp[i][j]来表示到[i][j]时，可以得到的花生数的集合，它的值表示这些值中的最大值。

然后是状态计算，显然每个值只有两个状态来更新它，

从上方来：dp[i][j]=dp[i-1][j]+w[i][j]

从左边来：dp[i][j]=dp[i][j-1]+w[i][j]

所以dp[i][j]=max(dp[i-1][j],dp[i][j-1])+w[i][j]

最后考虑边界值的处理，我们的数组下标从1开始，那么边界的位置都是0，不会影响和的计算，不用做什么处理。

#include<bits/stdc++.h>
using namespace std;
int dp[120][120],w[120][120];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        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]);
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+w[i][j];
            }
        }
        printf("%d\n",dp[n][m]);
    }
}

?ps:突然想到一些跟这道题没什么关系的，A->B有两个决策，那么岂不是可以与贪心联系起来，但是贪心一般从A的角度来考虑最佳策略，而动态规划则是从B的角度来考虑如何从A推B，这里如果看A->B,后面要假设的情况太多，如果全部讨论一下，实际上是一棵二叉树，所以实际上如果数据范围够小的话，搜索也可以解决，最短路问题。动态规划的话实际上算是一种优化，但是使用的条件是用来更新B的状态比较简单或者有规律可以很容易地算出来。简单概括，正着算就是贪心或是最短路，取决于当前决策实际产生地影响可不可以缩小，反正算就是动态规划，用前面更新后面。比如?Three Activities（Problem - D - Codeforces）这个题就是用dfs解决的非图问题。因为我们讨论一下就会发现画出来的三个树规模都很小。

1018. 最低通行费（活动 - AcWing）

题目大意：有一个n*n的大方格，每穿越一个方格都会花费时间1，我们最多只能花费时间(2*n-1)，每个方格都有一个最低通行费，我们需要求出从左上角方格到右下角方格的最低通行费。

思路：这道题乍一看没有说每个一步有几个操作，好像跟数字三角形联系不起来，但我们仔细想想，这个最多只能花费时间2*n-1是什么意思，我们讨论一下，想要最快到达肯定是不走回头路，那么我们就沿边界走一遍看看，显然花费的时间就是2n-1，那么就明白了，我们不能走回头路，也即只能向下或者向右移动，那么就是数字三角形问题。与摘花生问题的分析一致，但有一点不同，这里是求最小花费，而摘花生是求最大值，所以涉及到边界的处理是不一样的，当然我们也可以将第一行和第一列预处理一下。

#include<bits/stdc++.h>
using namespace std;
int w[120][120],f[120][120];
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++) f[1][i]=f[1][i-1]+w[1][i];
    for(int i=1;i<=n;i++) f[i][1]=f[i-1][1]+w[i][1];
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=n;j++)
        {
            f[i][j]=min(f[i-1][j],f[i][j-1])+w[i][j];
        }
    }
    printf("%d",f[n][n]);
}

1027. 方格取数（活动 - AcWing）

题目大意：从左上角到右下角，走两遍，但一个格子中的数只能取一次。问取出来的数的和的最大值是多少。

思路：这个题和上面就有所不同了，上面都是只走一遍，但这里却要走两遍，而且一个格子中的数，只能被取一次。当然有一个思路是先走一遍，同时记录路径，然后将路径上的点置0，然后再走一遍。不是不可以，只是有点麻烦，我们还有一个思路，就是两个同时走，两者路径重合时的那个点只取一次即可。那么我们可以定义dp[i1][j1][i2][j2]表示从1走到[i1,j1],[i2,j2]的最大和，但是四维更新属实麻烦，我们压缩一下，显然两个同时走的话，同一时刻的步数是相同的，那么我们用k来表示步数，则j1=k-i1,j2=k-i2，于是四维就被压成三维，dp[k][i1][i2]表示走了k步之后，到i1和i2两个位置产生的和，值表示这些和的最大值。

然后就是状态更新，每个点有两种操作，那么两个点就有四种操作：

我们要考虑i1是否等于i2,因为相同的点只能加一次

t=w[i1][k-i1]

if(i1!=i2) t+=w[i2][k-i2]

下下：dp[k][i1][i2]=dp[k-1][i1-1][i2-1]+t

下右：dp[k][i1][i2]=dp[k-1][i1-1][i2]+t

右下：dp[k][i1][i2]=dp[k-1][i1][i2-1]+t

右右：dp[k][i1][i2]=dp[k-1][i1][i2]+t

那么我们dp[k][i1][i2]就是它们的最大值

#include<bits/stdc++.h>
using namespace std;
int f[40][20][20],w[20][20];
int main()
{
    int n;
    scanf("%d",&n);
    int a,b,c;
    while(scanf("%d%d%d",&a,&b,&c))
    {
        if(!a&&!b&&!c) break;
        w[a][b]=c;
    }
    for(int k=1;k<=2*n;k++)
    {
        for(int i1=1;i1<=n;i1++)
        {
            for(int i2=1;i2<=n;i2++)
            {
                int j1=k-i1,j2=k-i2;
                if(1<=j1&&j1<=n&&1<=j2&&j2<=n) 
                {
                    int t=w[i1][j1];
                    if(i1!=i2) t += w[i2][j2];
                    int &x=f[k][i1][i2];
                    x = max(x,f[k-1][i1-1][i2-1]+t);
                    x = max(x,f[k-1][i1-1][i2]+t);
                    x = max(x,f[k-1][i1][i2-1]+t);
                    x = max(x,f[k-1][i1][i2]+t);
                }
            }
        }
    }
    printf("%d",f[n+n][n][n]);
}

?ps:这里最关键的就是意识到两个点可以同时走，我们可以用这里产生的一个相同值——步数来压缩维数，另外把重叠情况处理好即可。

275. 传纸条(275. 传纸条 - AcWing题库)

题目大意：

这个题乍一看和方格取数差不多，但是有一点不同，方格取数没有强制要求取过数的方格不能再踩，但是这里却要求，每个点只能过一次，不过我们两边能走的点数是有限的，要想使总的结果最大，肯定不能重复，而我们搜出来的就是结果的最大值，所以也一定没有重复。进而直接用方格取数的思路即可。

#include<bits/stdc++.h>
using namespace std;
int f[120][60][60],w[60][60];
int main()
{
    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 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(1<=j1&&j1<=m&&1<=j2&&j2<=m) 
                {
                    int t=w[i1][j1];
                    if(i1!=i2) t += w[i2][j2];
                    int &x=f[k][i1][i2];
                    x = max(x,f[k-1][i1-1][i2-1]+t);
                    x = max(x,f[k-1][i1-1][i2]+t);
                    x = max(x,f[k-1][i1][i2-1]+t);
                    x = max(x,f[k-1][i1][i2]+t);
                }
            }
        }
    }
    printf("%d",f[n+m][n][n]);
}

这种题很容易在不能只能用一次的那个地方纠结，但是我们宏观来看，重复肯定会浪费次数，我们一定每一步都取到数才是最优的，所以当细节纠结时，不妨宏观看看能否否定这个细节的出现。

当然这类题还可以延伸成走k次，那么就成费用流问题了，等我学到那里再来贴个链接。