方格取数问题

1. 概述

• 给定一个 $n\times m$ 的矩阵，每个位置有个非负数，我们可以从左上角走到右下角，每经过一个位置我们可以把格子上对应的数字取走，取走之后数字变为0，问我们可以获得的数字之和最大是多少？

• 此问题存在递进的三种类型：

  • （1）可以从左上角走到右下角1次，对应题目：AcWing 1015. 摘花生；

  • （2）可以从左上角走到右下角2次，对应题目：AcWing 1027. 方格取数、Leetcode 0741 摘樱桃；

  • （3）可以从左上角走到右下角k次，对应题目：AcWing 382. K取方格数。

2. AcWing上对应题目

AcWing 1015. 摘花生

问题描述

• 问题链接：AcWing 1015. 摘花生

分析

• 动态规划，分析如下：

代码

• C++

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

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

int main() {
    
    int T;
    cin >> 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;
}

AcWing 1027. 方格取数

问题描述

• 问题链接：AcWing 1027. 方格取数

分析

• 本题中两条路径不是独立的，因此不能首先求一条，然后标记上之后不能使用，然后再遍历第二条。因此要同时求解。

• 我们可以定义状态：f[i1, j1, i2, j2]表示所有从(1, 1)分别走到(i1, j1)、(i2, j2)的路径的最大值。那么我们应该如何处理同一个格子不能被重复选择的问题？考虑什么时候两条路径的格子可能重合，当i1+j1==i2+j2的时候两个格子可能重合（当然满足这个条件也可能不重合）。

• 因此我们可以使用f[k, i1, i2]表示所有从(1, 1)分别走到(i1, k-i1)、(i2, k-i2)的路径的最大值。k表示两条路线当前走到的格子的横纵坐标之和，即k=i1+j1=i2+j2。

• 考虑状态转移，可以根据两条路线到达(i1, k-i1)、(i2, k-i2)的前一步分为四种情况，如下图：

• 我们在这四类中求出最大值就是对应的f(k, i1, i2)。

代码

• C++

#include <iostream>

using namespace std;

const int N = 15;

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

int main() {
    
    scanf("%d", &n);
    int a, b, c;
    while (cin >> a >> b >> c, a || b || c) w[a][b] = c;
    
    for (int k = 2; k <= n * 2; 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];  // 说明(i1, j1)、(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\n", f[n * 2][n][n]);
    
    return 0;
}

AcWing 382. K取方格数

问题描述

• 问题链接：AcWing 382. K取方格数

分析

• 本题是一个费用流的问题。

• 每个方格看成原图中的一个点，需要拆点，每个点拆成入点和出点，入点和出点之间添加两条有向边：入点到出点的容量为1费用为方格中数的有向边（表示只能取一次方格中的数），入点到出点容量为正无穷费用为0的有向边（表示可以通过该点多次）。

• 从虚拟源点S向(0, 0)的入点连接一条有向边，容量为k，费用为0；从(n-1, n-1)的出点向虚拟汇点T连接一条有向边，容量为k，费用为0。

• 对新图求一遍最大费用最大流即可得到答案。

• 方格的编号：(0, 0)的到的两个点编号为0、1，(0, 1)的到的两个点编号为2、3，依次类推。

代码

• C++

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5010, M = 20010, INF = 1e8;

int n, k, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];

void add(int a, int b, int c, int d) {
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}

// t为0表示入点，t为1表示入点
int get(int x, int y, int t) {
    return (x * n + y) * 2 + t;
}

bool spfa() {
    
    int hh = 0, tt = 1;
    memset(d, -0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    
    int cnt = 0;
    
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;
        
        for (int i = h[t]; ~i; i = ne[i]) {
            int ver = e[i];
            if (f[i] && d[ver] < d[t] + w[i]) {
                d[ver] = d[t] + w[i];
                pre[ver] = i;
                incf[ver] = min(f[i], incf[t]);
                if (!st[ver]) {
                    q[tt++] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}

int EK() {
    
    int cost = 0;
    while (spfa()) {
        int t = incf[T];
        cost += t * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1]) {
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
    return cost;
}

int main() {
    
    scanf("%d%d", &n, &k);
    S = 2 * n * n, T = S + 1;
    memset(h, -1, sizeof h);
    
    add(S, get(0, 0, 0), k, 0);
    add(get(n - 1, n - 1, 1), T, k, 0);
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            int c;
            scanf("%d", &c);
            add(get(i, j, 0), get(i, j, 1), 1, c);  // 拆点
            add(get(i, j, 0), get(i, j, 1), INF, 0);  // 拆点
            if (i + 1 < n) add(get(i, j, 1), get(i + 1, j, 0), INF, 0);
            if (j + 1 < n) add(get(i, j, 1), get(i, j + 1, 0), INF, 0);
        }
    
    printf("%d\n", EK());
    
    return 0;
}

3. 力扣上对应题目

Leetcode 0741 摘樱桃

问题描述

• 问题链接：Leetcode 0741 摘樱桃

  

分析

• 本题的考点：动态规划。

• 本题中两条路径不是独立的，因此不能首先求一条，然后标记上之后不能使用，然后再遍历第二条。因此要同时求解。本题中动态规划中的数组对应左上角的坐标为(1, 1)。

• 我们可以定义状态：f[i1, j1, i2, j2]表示所有从(1, 1)分别走到(i1, j1)、(i2, j2)的路径的最大值。那么我们应该如何处理同一个格子不能被重复选择的问题？考虑什么时候两条路径的格子可能重合，当i1+j1==i2+j2的时候两个格子可能重合（当然满足这个条件也可能不重合）。

• 因此我们可以使用f[i1, i2, k]表示所有从(1, 1)分别走到(i1, k-i1)、(i2, k-i2)的路径的最大值。k表示两条路线当前走到的格子的横纵坐标之和，即k=i1+j1=i2+j2。

• 为了方便，这里状态定义为重新写为f[i, j, k]，因此表示从(1, 1)分别走到(i, k-i)、(j, k-j)的路径的最大值。

• 考虑状态转移，可以根据两条路线到达(i, k-i)、(j, k-j)的前一步分为四种情况，如下图：

• 本题中还需要考虑如果两条路线中有格子不合法怎么办？直接跳过即可。

• 因为(i, k - i)要在格子中，因此1<=i<=n && 1<=k-i<=n，因此max(1, k-n)<=i<=min(n, k-1)。同理max(1, k-n)<=j<=min(n, k-1)。

代码

• C++

const int N = 55;
int f[N][N][N * 2];

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {

        int n = grid.size();
        memset(f, -0x3f, sizeof f);
        f[1][1][2] = grid[0][0];
        for (int k = 3; k <= n * 2; k++)
            for (int i = max(1, k - n); i <= min(n, k - 1); i++)
                for (int j = max(1, k - n); j <= min(n, k - 1); j++) {
                    
                    if (grid[i - 1][k - i - 1] == -1 || grid[j - 1][k - j - 1] == -1) continue;
                    
                    int t = grid[i - 1][k - i - 1];
                    if (i != j) t += grid[j - 1][k - j - 1];
                    
                    for (int a = i - 1; a <= i; a++)
                        for (int b = j - 1; b <= j; b++)
                            f[i][j][k] = max(f[i][j][k], f[a][b][k - 1] + t);
                }
        
        return max(0, f[n][n][n * 2]);
    }
};

• Java

class Solution {

    static final int N = 55;
    int[][][] f = new int[N][N][N * 2];

    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                Arrays.fill(f[i][j], (int) -1e8);
        f[1][1][2] = grid[0][0];
        for (int k = 3; k <= n * 2; k++)
            for (int i = Math.max(1, k - n); i <= Math.min(n, k - 1); i++)
                for (int j = Math.max(1, k - n); j <= Math.min(n, k - 1); j++) {
                    if (grid[i - 1][k - i - 1] == -1 || grid[j - 1][k - j - 1] == -1) continue;
                    int t = grid[i - 1][k - i - 1];
                    if (i != j) t += grid[j - 1][k - j - 1];
                    for (int a = i - 1; a <= i; a++)
                        for (int b = j - 1; b <= j; b++)
                            f[i][j][k] = Math.max(f[i][j][k], f[a][b][k - 1] + t);
                }
        return Math.max(0, f[n][n][n * 2]);
    }
}

• Python

# TLE
class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        N = 55
        f = [[[(int) (-1e8) for _ in range(N * 2)] for _ in range(N)] for _ in range(N)]
        f[1][1][2] = grid[0][0]
        for k in range(3, n * 2 + 1):
            for i in range(max(1, k - n), min(n, k - 1) + 1):
                for j in range(max(1, k - n), min(n, k - 1) + 1):
                    if grid[i - 1][k - i - 1] == -1 or grid[j - 1][k - j - 1] == -1:
                        continue
                    t = grid[i - 1][k - i - 1]
                    if i != j:
                        t += grid[j - 1][k - j - 1]
                    for a in range(i - 1, i + 1):
                        for b in range(j - 1, j + 1):
                            f[i][j][k] = max(f[i][j][k], f[a][b][k - 1] + t)
        return max(0, f[n][n][n * 2])

时空复杂度分析

• 时间复杂度：$O(n^3)$，n为数组边长。

• 空间复杂度：$O(n^3)$。