跳转至

数字三角形模型

DP 的思考方式:

  1. 阶段
  2. 决策
  3. 最优子结构
  4. 无后效性

DP 设计角度:

  • 动态规划
    • 状态表示: f[i,j]
      • 集合: 本质是 一个数表示一类状态
      • 属性: Max OR Min OR Count
    • 状态计算: 集合的划分
      • 很重要的划分依据: “最后一步”
      • 集合划分的依据: 不重(看情况, 比如求max就可以重) + 不漏(必须)

一般 DP 状态设计:

  1. 线性: f[i]
  2. 二维: f[i,j]
  3. 背包: f[i,j]

提升速度:

C++
1
2
ios::sync_with_stdio(false);
cin.tie(0);

1015 摘花生

  • 状态表示: f[i,j]
    • 集合: 所有从 [1,1] 走到 [i,j] 的路线
    • 属性: Max OR Min OR Count
  • 状态计算: 集合的划分
    • 很重要的划分依据: “最后一步”
C++
 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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int w[N][N];
int f[N][N];

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        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], f[i][j - 1]) + w[i][j];

        printf("%d\n", f[n][m]);
    }

    return 0;
}

1018 最低通行费

必须 2N-1: 说明只能 “向下” or “向右”（不能走回头路）

注意

这题不同于摘花生的地方在于，他的属性是最小值，因此需要在代码上作出一点点改变

例如，需要 先把所有状态初始化为正无穷，初始化状态的起点（dp求最小值必须要的步骤）

以及， 状态转移时的越界判断

C++
 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
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int n;
int w[N][N];
int f[N][N];

int main()
{
    //input
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            cin >> w[i][j];
        }
    }

    //initialize
    memset(f, 0x3f, sizeof f);
    f[1][1] = w[1][1];

    //dp
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            // 只有不在第一行的时候，才可以从上面过来
            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]);
        }
    }

    //output
    cout << f[n][n] << endl;

    return 0;
}

1027 方格取数

  • 只能 “向下” 或 “向右”
  • "走过后 就 不能再走" 等价于: 并行走两条, 反正要求仅仅是不会重合
    • 显然: 任一时间快照, 二者的总步数相等

如何处理 "同一个格子不能被重复选择"

只有当 i1+j1 ==i2+j2 时, 两条路径的格子才可能重合

因此可以优化维度: f[i1][j1][i2][j2] ---> f[k][i1][i1]. (基于 "任一时间快照, 二者的总步数相等")

动态规划

C++
 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
37
38
39
40
41
42
43
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
int w[N][N];
int f[N * 2][N][N];

int main()
{
    scanf("%d", &n);

    int a, b, c;

    // 循环输入, input不为0的写法
    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)
                {
                    // 重合 iff (i1==i2 && j1==j2)
                    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);
                    f[k][i1][i2] = x;
                }
            }

    printf("%d\n", f[n + n][n][n]);
    return 0;
}