【算法初步——超容易的动态规划（1）：数字三角形模型】_动态规划 交叉点

算法初步——超容易的动态规划（1）：数字三角形模型

---

前言

时隔一年，在不久前学习完离散数学后便想着再次趁着超长寒假来继续学习算法~

这一系列将从之前报名的Acwing算法提高课选题，笔者会把这项课程分拆开来讲解清楚 ！

希望能够帮助到各位快速上手算法~

---

一、问题1：摘花生

原问题链接

解题思路

本题实际上使用递归的思想。
和我们在数列里面学到的数列递推公式是异曲同工之妙
$$a_n=k{a}_{n-1}+b（这里k，b为常数）$$
如果有这个公式，还有a1，那么就必然可以求an

对于本题，递归就可以运用在第（n，m）格摘花生时的最大摘取量和在（n-1，m），（n，m-1）格摘花生时的最大摘取量的递推关系式求解。

我们设在（n，m）格摘花生时的最大摘取量为f[ n ][ m ],在 （n，m）格上有花生a[ n ][ m ]颗，我们就能列写出这样的公式（因为我们只能摘右边的或者下面的花生）：

f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
1

因为我们本身知道在（1，1）格摘花生的最大摘取量就是它本身

代码如下：

#include <iostream>
using namespace std;
const int N = 105;  //定义N超过100，使得空间足够
int a[N][N],f[N][N];
int num,row,col;

int main(){
    cin>>num;
    
    //键入花生所在处，这里采用num来判断是否按照指定要求键入完全
    
    while(num--){
        cin>>row>>col;
        for(int i = 1;i<=row;i++){
            for(int j = 1;j<=col;j++){
                cin>>a[i][j];
            }
        }
        
        // 遍历所有的格数，满足我们的递推关系：
        //在第（n，m）格摘花生时的最大摘取量和在（n-1，m），（n，m-1）格摘花生时的最大摘取量
        
        for(int i = 1;i<= row;i++){
            for(int j = 1;j<=col;j++){
                f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
            }
        }
        cout<<f[row][col]<<endl;  //输出花生摘取量
    }
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

成功AC！

---

二、问题2：最低通行费

原题链接

解题思路

本题实际上和摘花生思路一致。摘花生要求最大的采摘量，这题就相当于求最小的采摘量。我们只用把max函数换成min函数即可，这里就不做详细赘述了，直接上代码！

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 105;  //扩展
int n;
int a[N][N];
int f[N][N]; 
int main()
{
    //键入每个地方的费用
    
    cin >> n;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j) cin >> a[i][j];

    //初始化f[1][1]的值为a[1][1],设置为0x3f是为了保证无穷大不会溢出，当然可以写0x3f3f3f3f3f...
    
    memset(f, 0x3f, sizeof f);
    f[1][1] = a[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]+a[i][j],f[i][j-1]+a[i][j]});
            //（因为不用特判起点了，要加f[i][j]，注意这样写要加入 #include <algorithm>）
            
            //这里也可以这么写
            //f[i][j] = min(f[i][j], f[i - 1][j] + a[i][j]);
            //f[i][j] = min(f[i][j], f[i][j - 1] + a[i][j]);
        }
    }
    cout << f[n][n] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

成功AC！

注：这题要注意的是必须要提前对字节单位开辟一个memset（看了ACwing大佬的激烈讨论后得出的结论）

---

三、问题3：方格取数

解题思路

在我们看到这道方格取数问题时，深入思考后不难发现其实是一道结合了两个摘花生问题的题目。但这道题的限制是，在我们取完一个方格的数后，这个数变为0.也就是不能单纯地把摘花生问题的结果乘2！即路径重合处我们需要减去一个重复计算的值

$$\begin{gathered} 比如在这个图里面，我们想从A点走到B点，有黑线和蓝线两条选择。 \\ 但是其中势必会经过C和D点这两个交叉点。有两个人（姑且称为小黑和小蓝）， \\ 其中小黑先出发，他从C点已经拿到了自己的数字，那么C点就没数字可拿了， \\ 小蓝出发走到C点，发现这里空空如也，一个数字都不剩下了 \end{gathered}$$
$$\begin{gathered} 采花生问题我们默认采的总数就是小黑走的所有数字+小蓝走的所有数字 \\ （怎么采花生总数不会受到影响），而这里采的总数就要变成小黑走的所 \\ 有数字+小蓝走的所有数字-重复点C的数字-重复点D的数字 \end{gathered}$$
$$\begin{gathered} 那该怎么办呢？ \\ 我们还是回归到本质上，从我们说的“递归”入手。 \end{gathered}$$

$$\begin{gathered} 如果把这道题目的递归项从f[i][j]变成f[i_1][j_1][i_2][j_2]， \\ 其中（i1，j1）和（i2，j2）指终点 \end{gathered}$$
$$\begin{gathered} 那么问题就转化成了四维数组。但这看上去很难受， \\ 而且我们不好说明i_1=i_2且j_1=j_2时（重复点）怎么减去 \end{gathered}$$
$$\begin{gathered} 这里巧妙的一点就是引入相关量“k”。其中k=i_1+j_1=i_2+j_2。把方程改写为 \\ f[k][i_1][i_2] \end{gathered}$$
$$如果i1=i2，那么就说明小黑和小蓝走过了同一个交叉点，反之则路线没有相交$$

代码如下：

//算法一：采用i1，i2，k实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int n,w[N][N],f[N*2][N][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,j2 = k-i2;
                if(j1>=1 && j1<=n && j2>=1 && 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);
                }
            }
    cout<<f[n+n][n][n]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

//算法二：采用i1，j1，i2实现，不引入k，原理是一样的
#include <iostream>
#include <cstring>
using namespace std;
const int N=15;
int main(){
    int num;
    cin>>num;
    int x,y,z,a[N][N],f[N][N][N];
    
    //键入，当键入000终止采用while（x||y||z）
    
    while(cin>>x>>y>>z,x||y||z) a[x][y]=z;
    
    //采用j1而不采用k，结果一致
    
    for(int i1=1;i1<=num;i1++){
        for(int j1=1;j1<=num;j1++){
            for(int i2=1;i2<=num;i2++){
                int j2=i1+j1-i2;
                if(j2>=1 && j2<=num){
                    //这里用temp找到最大值，四种情况分别对应右右，右下，下右，下下
                    int tmp= max(f[i1-1][j1][i2],f[i1-1][j1][i2-1]);
                    tmp =max(tmp,f[i1][j1-1][i2]);
                    tmp =max(tmp,f[i1][j1-1][i2-1]);
                    f[i1][j1][i2]=tmp +a[i1][j1]+a[i2][j2];
                    if(i1 == i2) f[i1][j1][i2]=tmp +a[i1][j1];
                }
            }
        }
    }
    cout<<f[num][num][num]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

成功AC！

---

四、问题4：传纸条

原题链接

解题思路

这道题实际就是上一道方格取数的翻版，原理都是一模一样的啦~

这里我们只用把传纸条的好感度设为上一题中的数字，传完一个纸条，那个人的好感度变为0可以理解为“取走了那个数”，那么自然而然地，这道问题就变成了方格取数问题~

直接上代码！

代码如下：

#include <iostream>
using namespace std;
int a[55][55];
int f[55*2][55][55];

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>a[i][j];

    for(int k=2;k<=n+m;k++){
        for(int i=1;i<k;i++){
            for(int j=1;j<k;j++){
                int &v = f[k][i][j];
                int tmp = a[i][k-i];
                if(i!=j){
                    tmp += a[j][k-j];
                }
                v = max(f[k - 1][i - 1][j], v);
                v = max(f[k - 1][i - 1][j - 1], v);
                v = max(f[k - 1][i][j - 1], v);
                v = max(f[k - 1][i][j], v);
                v += tmp;    
            }
        }
    }
    cout<<f[n+m][n][n]<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

成功AC！

---

总结

在这次的模型中，感觉用到的时一种“集合”的思想，能用一种集合将全事件表示清楚，然后将这个事件用递推去完整实现就是我们的思路。