数字三角形模型（动态规划）

​
​

活动地址：CSDN21天学习挑战赛

数字三角形模型

数字三角形模型是线性dp问题中一个重要的分支，主要用来处理二维的线性dp问题

二维的dp问题就可以很好的解决一些dfs的连通块问题所带来的tle

本来刚看到这种题的时候，我是想用dfs来写，然后发现根本用不着回溯，所以在不用从后往前传递值的情况下不要想着dfs,这样就帮助了我更好的确定做题的方法。

acwing算法提高课的第一章，数字三角形模型。相当于给一个矩阵，从左上角到右下角只能向下或向右遍历，寻求最优解。

1. acwing 1015 摘花生

点击跳转至题目 ： 摘花生
题目中，HelloKitty只能向东或向南走。每一个点都有若干花生，求HelloKitty 从左上角到右下角最多能拿多少花生给她喜欢的米老鼠。
典型的数字三角型模型解题思路：定义两个数组分别记录矩阵中的权值和每一个点的最优解，然后循环遍历矩阵中的每一个点，这样最后遍历到右下角的时候一定是最优解。
在遍历的时候，分 三种情况：

1. 在第一行 （i == 1 && j > 1）
2. 在第一列 (j == 1 && i > 1)
3. 不在第一行也不在第一列(i > 1 && j > 1)

#include
using namespace std ;
const int N = 110 ;
int q[N][N] , f[N][N];
int main()
{
    int t ;
    cin >> t ;
    while(t--)
    {
        int r, c ;
        cin >> r >>c;
        for(int i = 1 ; i <= r ; i++)
        {
            for(int j = 1 ; j <= c ; j++)
            {
                cin >> q[i][j];
            }
        }
        f[1][1] = q[1][1];
        for(int i = 1 ; i <= r ; i++)
        {
            for(int j = 1 ; j <= c ; j++)
            {
                if(i > 1 && j == 1) f[i][j] = f[i-1][j] + q[i][j];
                if(j > 1 && i == 1) f[i][j] = f[i][j-1] + q[i][j];
                if(j > 1 && i > 1) f[i][j] = max(f[i-1][j] + q[i][j],f[i][j-1] + q[i][j]);
            }
        }
        cout << f[r][c] << 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

2. acwing 1018 最低通行费

点击跳转至题目： 最低通行费
解题思路：
这道题的类型跟摘花生一样的套路，只不过题目变了。

#include
#include
using namespace std ;
const int N = 110 ;
int q[N][N] , f[N][N];
int n ;
int main()
{
    cin >> n ;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            cin >> q[i][j];
        }
    }
    f[1][1] = q[1][1];
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            if(i == 1 && j > 1 ) f[i][j] = f[i][j-1] + q[i][j];
            if(j == 1 && i > 1 ) f[i][j] = f[i - 1][j] + q[i][j];
            if(i > 1 && j > 1) f[i][j] = min(f[i][j-1] + q[i][j],f[i - 1][j] + q[i][j]);
        }
    }
    cout << f[n][n];
    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

3. acwing 1027 方格取数

点击跳转至题目： 方格取数
解题思路：
题意是从A到B，一共走了两次，当走过一个点时，方格中的数字就会变成数字 0
错误思路 ×：想当然先走一遍，然后把走过的方格元素变成0，然后走第二遍。

https://www.acwing.com/user/myspace/index/64630/ 糖豆
下图借用了acwing 评论中 糖豆用户的评论

所以，我们要让两次同时走，尽可能一起取最优解。
解决方案：两个路线就证明有两个点：设为i1，i2
i1 + j1 == i2 + j2 ，因为有四个元素，那状态函数就会是四维，这里让 k = i1 + j1 = i2 + j2 ，这样两个点的坐标就变成了 （i1，k-i1） （i2，k-i2）
遍历过程中，两个点可能在或不在同一个点，若是不在同一个点，那两个值都要加上

#include
using namespace std;
const int N = 20;
int f[2*N][N][N] ,  w[N][N];
int main()
{
    int n ;
    cin >> n ;
    int a , b , c ;
    while(cin >> a>> b >> c , a||b||c) w[a][b] = c ;
    for(int k = 2 ; k <= 2*n ; k++)
    {
        for(int i1 = 1 ; i1 <= n ; i1++)
        {
            for(int i2 = 1 ; i2 <= n ; i2++)
            {
                int t = w[i1][k-i1];
                if(i1 != i2) t += w[i2][k-i2];
                int &x = f[k][i1][i2];
                x = max(x,f[k-1][i1-1][i2-1] + t);
                x = max(x,f[k-1][i1][i2-1] + t);
                x = max(x,f[k-1][i1-1][i2] + t);
                x = max(x,f[k-1][i1][i2] + t);
            }
        }
    }
    cout << f[2*n][n][n];
    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

4. acwing 275 传纸条

点击跳转至题目： 传纸条
这道题跟方格取数差不多，比方格取数多了以下几点：

1. 不是正方形矩阵，当遍历横坐标的时候，要考虑纵坐标是否符合
2. 最后的结果是f[n+m][n][n],两个都是横坐标，而不是f[n+m][n][m]
   i1 >= 1
   i1 <= n
   k - i1 >= 1
   k - i1 <=m
   所以出现了遍历时候的min和max

#include
using namespace std;
const int N = 55;
int f[2*N][N][N] ,  w[N][N];
int main()
{
    int n , m ;
    cin >> n >> m;
    for(int i = 1 ; i <= n; i++)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            cin >> w[i][j];
        }
    }
    for(int k = 2 ; k <= n + m ; k++)
    {
        for(int i1 = max(1,k - m) ; i1 <= min(k - 1 , n); i1++)
        {
            for(int i2 = max(1,k-m) ; i2 <= min(k - 1 , n) ; i2++)
            {
                int t = w[i1][k-i1];
                if(i1 != i2) t += w[i2][k-i2];
                int &x = f[k][i1][i2];
                x = max(x,f[k-1][i1-1][i2-1] + t);
                x = max(x,f[k-1][i1][i2-1] + t);
                x = max(x,f[k-1][i1-1][i2] + t);
                x = max(x,f[k-1][i1][i2] + t);
            }
        }
    }
    cout << f[n+m][n][n];
    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