LeetCode741. 摘樱桃
题目描述
本题目来自LeetCode上的『741. 摘樱桃』
一个N x N的网格(grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来表示：
- 0 表示这个格子是空的，所以你可以穿过它。
- 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
- -1 表示这个格子里有荆棘，挡着你的路。
你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃：
- 从位置 (0, 0) 出发，最后到达 (N-1, N-1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为0或者1的格子）；
- 当到达 (N-1, N-1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
- 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为0）；
- 如果在 (0, 0) 和 (N-1, N-1) 之间不存在一条可经过的路径，则没有任何一个樱桃能被摘到。
示例1：
输入: grid =
[[0, 1, -1],
[1, 0, -1],
[1, 1, 1]]
输出: 5
解释：
玩家从（0,0）点出发，经过了向下走，向下走，向右走，向右走，到达了点(2, 2)。
在这趟单程中，总共摘到了4颗樱桃，矩阵变成了[[0,1,-1],[0,0,-1],[0,0,0]]。
接着，这名玩家向左走，向上走，向上走，向左走，返回了起始点，又摘到了1颗樱桃。
在旅程中，总共摘到了5颗樱桃，这是可以摘到的最大值了。
提示
grid是一个N*N的二维数组，N的取值范围是1 <= N <= 50。- 每一个
grid[i][j]都是集合{-1, 0, 1}其中的一个数。 - 可以保证起点
grid[0][0]和终点grid[N-1][N-1]的值都不会是 -1。
题解1 - 记忆化搜索
原题等价于两个人同时从起点开始摘樱桃，最终到达终点所能摘的樱桃的最大数量。
设递归函数 dfs(x1, y1, x2, y2) 为两个人分别从 $(x1,y1)$ 和 $(x2,y2)$ 开始，到达终点所摘樱桃总数。每次只需要向后搜索 $(x1+1,y1)(x2+1,y2)$、$(x1,y1+1)(x2+1,y2)$、$(x1+1,y1)(x2,y2+1)$、$(x1,y1+1)(x2+1,y2+1)$ 四个情况。
剪枝1： 当 $(x1,y1)$ 或 $(x2,y2)$ 超出边界时需要剪枝。当 $(x1,y1)$ 或 $(x2,y2)$ 所在位置为荆棘时需要剪枝。
剪枝2： 两个人 A 和 B，在任意时刻，交换 A 和 B 的位置继续搜索，不会对结果产生影响，因为两者是等价的。因此，让 B 始终在 A 的下方搜索，可以减少递归次数。
代码
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
@cache
def dfs(x1: int, y1: int, x2: int, y2: int) -> int:
if x1 == n - 1 and y1 == n - 1:
return grid[x1][y1]
ret = float('-inf')
for nx1, ny1 in [[x1 + 1, y1], [x1, y1 + 1]]:
if nx1 < 0 or nx1 >= n or ny1 < 0 or ny1 >= n:
continue
if grid[nx1][ny1] == -1:
continue
for nx2, ny2 in [[x2 + 1, y2], [x2, y2 + 1]]:
if nx2 < 0 or nx2 >= n or ny2 < 0 or ny2 >= n:
continue
if nx2 > nx1:
continue
if grid[nx2][ny2] == -1:
continue
ret = max(ret, dfs(nx1, ny1, nx2, ny2))
return ret + grid[x1][y1] + grid[x2][y2] if x1 != x2 else ret + grid[x1][y1]
n = len(grid)
ans = dfs(0, 0, 0, 0)
return ans if ans > float('-inf') else 0
复杂度分析
- 时间复杂度：$O(n^4)$，可优化
- 空间复杂度：$O(n^4)$
题解2 - 动态规划
注意到 $x1+y1=x2+y2=k$，因此上述题解1的四个状态可以优化为三个，设 $dp[k][x1][x2]$ 为每个人各走了 $k$ 步，分别到达 $(x1,k-x1)$ 和 $(x2,k-x2)$ 时所摘樱桃数量。状态 $dp[k][x1][x2]$ 可由下述四种情况转移而来：
- A 右 B 右：$dp[k-1][x1][x2]$
- A 下 B 右：$dp[k-1][x1-1][x2]$
- A 右 B 下：$dp[k-1][x1][x2-1]$
- A 下 B 下：$dp[k-1][x1-1][x2-1]$
取上述四种的最大值，再加上 $grid[x1][y1]$ 和 $grid[x2][y2]$，若 A 和 B 相遇只需要加一次 $grid[x1][y1]$。
$dp[k][x1][x2]$ 初始化每项为负无穷，为了方便处理边界，在最外圈加上一圈荆棘，即该处的 $dp$ 值为负无穷。
同样有题解1的 剪枝2： 两个人 A 和 B，在任意时刻，交换 A 和 B 的位置继续搜索，不会对结果产生影响，因为两者是等价的。因此，让 B 始终在 A 的下方搜索，可以减少递归次数。
空间优化： 由于 $dp[k]$ 的状态只与 $dp[k-1]$ 有关，可以使用滚动数组优化掉一层空间。
代码
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
N = 51
n = len(grid)
dp = [[-inf] * N for _ in range(N)]
dp[1][1] = grid[0][0]
for k in range(3, 2 * n + 1):
for x1 in range(n, 0, -1):
for x2 in range(n, x1 - 1, -1):
y1 = k - x1
y2 = k - x2
if y1 <= 0 or y1 > n or y2 <= 0 or y2 > n:
continue
if grid[x1 - 1][y1 - 1] == -1 or grid[x2 - 1][y2 - 1] == -1:
dp[x1][x2] = -inf
continue
a = dp[x1 - 1][x2]
b = dp[x1][x2 - 1]
c = dp[x1 - 1][x2 - 1]
d = dp[x1][x2]
t = max(a, max(b, max(c, d)))
t = t + grid[x1 - 1][y1 - 1] + grid[x2 - 1][y2 - 1] if x1 != x2 else t + grid[x1 - 1][y1 - 1]
dp[x1][x2] = t
return max(dp[n][n], 0)
复杂度分析
- 时间复杂度：$O(n^3)$
- 空间复杂度：$O(n^2)$
题解3 - 最大费用最大流
根据题意，有以下建图规则：
- 有两条路线，因此每条边的容量可设为 2。
- 将 $grid$ 中的每个元素解构为一个入点和一个出点，如果 $grid[i][j]=1$，在入点和出点直接设置一条容量为 1，费用为 1 的边，和一条容量为 1，费用为 0 的边,。前者表示摘樱桃，后者表示可通过。
- 如果 $grid[i][j]=0$，在入点和出点直接设置一条容量为 2，费用为 0 的边，表示可通过。
- 如果 $grid[i][j]\ge 0$，在 $grid[i][j]$ 和 $grid[i][j+1]$，$grid[i][j]$ 和 $grid[i+1][j]$ 直接分别设置一条容量为 2，费用为 0 的边，表示可通过。
- 设置一个超级源点，与 $grid[0][0]$ 之间有一条容量为 2，费用为 0 的边
- 设置一个超级汇点，与 $grid[n-1][n-1]$ 之间有一条容量为 2，费用为 0 的边
将图中的顶点编号为 $[1,n \times n + 2]$。对此图跑一次最大费用最大流，所得最大费用就是所能摘的最多的樱桃。
代码
class Solution {
private:
static constexpr int N = 5e3 + 5, M = 1e5 + 5;
static constexpr int INF = 0x3f3f3f3f;
int n, m, tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M], dis[N], ret;
bool vis[N];
void add(int u, int v, int w, int c) {
ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c;
}
void addedge(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); }
bool spfa(int s, int t) {
memset(dis, 0x3f, sizeof(dis));
memcpy(cur, lnk, sizeof(lnk));
std::queue<int> q;
q.push(s), dis[s] = 0, vis[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop(), vis[u] = 0;
for (int i = lnk[u]; i; i = nxt[i]) {
int v = ter[i];
if (cap[i] && dis[v] > dis[u] + cost[i]) {
dis[v] = dis[u] + cost[i];
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return dis[t] != INF;
}
int dfs(int u, int t, int flow) {
if (u == t) return flow;
vis[u] = 1;
int ans = 0;
for (int &i = cur[u]; i && ans < flow; i = nxt[i]) {
int v = ter[i];
if (!vis[v] && cap[i] && dis[v] == dis[u] + cost[i]) {
int x = dfs(v, t, std::min(cap[i], flow - ans));
if (x) ret += x * cost[i], cap[i] -= x, cap[i ^ 1] += x, ans += x;
}
}
vis[u] = 0;
return ans;
}
int mcmf(int s, int t) {
int ans = 0;
while (spfa(s, t)) {
int x;
while ((x = dfs(s, t, INF))) ans += x;
}
return ans;
}
public:
int cherryPickup(vector<vector<int>>& grid) {
int l = grid.size();
int ll = l * l;
int s = 1;
int t = ll * 2 + 2;
n = t;
addedge(s, 2, 2, 0);
addedge(ll * 2 + 1, t, 2, 0);
for (int i = 0; i < l; ++i) {
for (int j = 0; j < l; ++j) {
int tt = i * l + j + 2;
if (grid[i][j] >= 0) {
if (i + 1 < l) {
addedge(tt + ll, tt + l, 2, 0);
}
if (j + 1 < l) {
addedge(tt + ll, tt + 1, 2, 0);
}
}
if (grid[i][j] == 0) {
addedge(tt, tt + ll, 2, 0);
}
if (grid[i][j] > 0) {
addedge(tt, tt + ll, 1, -1);
addedge(tt, tt + ll, 1, 0);
}
}
}
mcmf(s, t);
return -ret;
}
};复杂度分析
- 时间复杂度：最坏情况下为 $O(n^2\times f)$，每次找增广路的复杂度为 $O(n\times n)$，$f$ 为最大流。
- 空间复杂度：$O(n)$
