动态规划之数字三角形模型

前言

数字三角形题型的一般描述是：

给定一个共有N行的三角矩阵A，其中第t行有X列。从左上角出发，每次可以向下方或右下方走一步，最终到达底部求把经过的所有位置上的某种最优情况

一般这类题的dp表达式都是：$f[i,j]$

最低通行费

题目转送门

首先我们定义：$f[i,j]$表示，从（1,1）走到（i，j）的最小花费，我们先不考虑时间是(2n-1)内，对于一个(i,j)我们可以从四个方向进入它，因此有 f[i][j] = min(f[i][j] , f[xx][yy] + a[i][j]) ; 我们按照这个dp式子交上去发现也可以ac，这是因为对于一个(i,j)来说我们在dp的时候是不会选择走回头路到（i，j）的也就是从下方和右方进入。
那么结合时间，我们发现我们在不走回头路的情况下都要（2n - 1）的单位时间，因此我们在考虑时间后可以不用考虑四个方位了。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110 ;
int n ;
int a[N][N] , f[N][N];
int dx[4] = {1,-1,0,0} , dy[4] = {0,0,1,-1};

int main(){
    cin>>n;
    memset(f , 0x3f , sizeof f);
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)cin>>a[i][j];
    f[1][1] = a[1][1];
    for(int i = 1  ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            for(int k = 0 ; k < 4 ; ++k){
                int xx = i + dx[k] , yy = j + dy[k];
                if(xx <= 0 && xx > n && yy <= 0 && yy > n)continue;
                f[i][j] = min(f[i][j] , f[xx][yy] + 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

方格取数

题目转送门

这题由走一篇的最大值，变成看走两遍的最大值（且不能重复取）。最开始的思路是先走第一篇取得一个最大值，然后标记之后再走一篇，两者相加，但是这个题贪心的让两次都最大并不一定是最优解，
如果遇到两次能把所有点都踩到的情况：
但由于第一次和第二次没有联系，第一次只取最优解，可能会导致第二次不能把剩下的点都踩到。
因此二维无法满足我们，那么我们就扩大维数，变成：$$f[k][i][j]$
k=i1+j1=i2+j2k=i1+j1=i2+j2 : 两个小朋友同时走, 每个人走的步数和是一样的
我们考虑集合划分

// 需要判断j是否越界！
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 15;
int n ;
int a[N][N] , f[N*2][N][N];

int main(){
    cin>>n;
       int x,y ,c;
       while(cin>>x>>y>>c , x || y ||c)
            a[x][y] = max(a[x][y],c);

    for(int k = 2 ; k <= n * 2 ; ++k)
        for(int i = 1 ; i <= n ; ++i)
            for(int j = 1 ;  j <= n ; ++j){
                int t = a[i][k-i] , &x = f[k][i][j] ;
                int j1 = k - i , j2 = k - j;
                if(j1 <= 0 || j1 > n || j2 <= 0 || j2 > n)continue;
                if(i != j ) t += a[j][k-j];
                x = max(x,f[k-1][i][j] + t);
                x = max(x,f[k-1][i][j-1] + t);
                x = max(x,f[k-1][i-1][j] + t);
                x = max(x,f[k-1][i-1][j-1] + t);
            }

    cout<< f[2*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
28
29
30
31
32

传纸条

题目转送门

题面分析：在这里我们可以转变一下思路，把求一条从(1,1) ->(n,m)和(n,m) - > (1,1)总共两条路径转化为，求两条从，(1,1) --> (n,m)的最大路径。那么这题就可以直接套用上一题的dp式子了。

要深刻理解dp表达式的含义

代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 55;
int n , m ;
int w[N][N] , f[N<<1][N][N];

int main(){
    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 i = 1; i <= n ; ++i)
            for(int j = 1 ; j <= n ; ++j){
                int t = w[i][k-i] + w[j][k-j] , &x = f[k][i][j];
                int j1 = k - i , j2 = k - j;
                if(j1 <= 0 || j1 > m || j2 <= 0 || j2 > m )continue;
                if(i != j || k == 2 || k == n + m){
                    x = max(x,f[k-1][i][j] + t);
                    x = max(x,f[k-1][i][j-1] + t);
                    x = max(x,f[k-1][i-1][j] + t);
                    x = max(x,f[k-1][i-1][j-1] + t);
                }
            }
    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