- Published on
算法001-网格图操作后的最大分数
- Authors
- Name
- i Joe
原题内容
给你一个大小为 n x n 的二维矩阵 grid ，一开始所有格子都是白色的。一次操作中，你可以选择任意下标为 (i, j) 的格子，并将第 j 列中从最上面到第 i 行所有格子改成黑色。 如果格子 (i, j) 为白色，且左边或者右边的格子至少一个格子为黑色，那么我们将 grid[i][j] 加到最后网格图的总分中去。
请你返回执行任意次操作以后，最终网格图的 最大 总分数。
- 示例 1：
输入：
grid = [[0,0,0,0,0],[0,0,3,0,0],[0,1,0,0,0],[5,0,0,3,0],[0,0,0,0,2]]
输出：
11
解释：
[图]
第一次操作中，我们将第 1 列中，最上面的格子到第 3 行的格子染成黑色。第二次操作中，我们将第 4 列中，最上面的格子到最后一行的格子染成黑色。最后网格图总分为 grid[3][0] + grid[1][2] + grid[3][3] 等于 11 。
- 示例 2：
输入：
grid = [[10,9,0,0,15],[7,1,0,8,0],[5,20,0,11,0],[0,0,0,1,2],[8,12,1,10,3]]
输出：
94
解释：
我们对第 1 ，2 ，3 列分别从上往下染黑色到第 1 ，4， 0 行。最后网格图总分为 grid[0][0] + grid[1][0] + grid[2][1] + grid[4][1] + grid[1][3] + grid[2][3] + grid[3][3] + grid[4][3] + grid[0][4] 等于 94 。
提示：
1 <= n == grid.length <= 100n == grid[i].length0 <= grid[i][j] <= 10^9
解题思路
- 取第j列的黑色格子占据多少格，决定这一列中能取的最大值。
- 第j列的有效白色格子有4种情况。
(1) 当j列=j+1列（默认为j列的黑色格子等于j+1列的黑色格子）
此时，j+1列并没有有效白色格子。
(2) 当j列<j+1列时
此时，多的计入j列。
(3) 当j列>j+1列>=j+2列时。
此时，多的计入j+1格子.
(4) 当j列>j+1列<j+2列时。
此时为凹形，一定只有j+1列全白最优，j+2不管多少个，都是会被枚举到，不管
解法1
long long maximumScore(vector<vector<int>>& grid) {
using ll = long long;
size_t n = grid.size();
// 每列前缀和
vector<vector<ll>> col_sum(n, vector<ll>(n + 1));
for (int j = 0; j < n; ++j) {
for (int i = 0; i < n; ++i) {
col_sum[j][i + 1] = col_sum[j][i] + grid[i][j];
}
}
vector<vector<array<ll, 2>>> dp(n - 1, vector<array<ll, 2>>(n + 1, {-1, -1}));
// pre表示j+1, dec表示j+1和j+2的大小，j+1小表示true
auto dfs = [&] (auto && dfs, int j, int pre, bool dec) -> ll {
if (j < 0) {
return 0;
}
auto& res = dp[j][pre][dec];
if (res != -1) return res;
res = 0;
// cur表示j有多少个黑格子
for (int cur = 0; cur <= n; ++cur) {
if (cur == pre) { //情况1: j = j+1
res = max(res, dfs(dfs, j - 1, cur, false));
} else if (cur < pre) { //情况2: j < j+1
res = max(res, dfs(dfs, j - 1, cur, true) + col_sum[j][pre] - col_sum[j][cur]);
} else if (!dec) { //情况3: j+1 >= j+2
res = max(res, dfs(dfs, j - 1, cur, false) - col_sum[j + 1][pre] + col_sum[j + 1][cur]);
} else if (pre == 0) { //情况4: j+1 < j+2
res = max(res, dfs(dfs, j - 1, cur, false));
}
}
return res;
};
// 枚举第n-1列有i个黑格
ll ans = 0;
for (int i = 0; i <= n; ++i) {
ans = max(ans, dfs(dfs, n - 2, i, false));
}
return ans;
}
此时，时间复杂度为O(n^3)，空间复杂度为O(n^2)
解法2
由于f[j][pre][dec] 和 dfs(j,pre,dec)一样，可以用该方法来解题
long long maximumScore(vector<vector<int>>& grid) {
using ll = long long;
size_t n = grid.size();
// 每列前缀和
vector<vector<ll>> col_sum(n, vector<ll>(n + 1));
for (int j = 0; j < n; ++j) {
for (int i = 0; i < n; ++i) {
col_sum[j][i + 1] = col_sum[j][i] + grid[i][j];
}
}
vector<vector<array<ll, 2>>> f(n, vector<array<ll, 2>>(n + 1));
// 枚举第n-1列有j个黑格
for (int j = 0; j < n - 1; ++j) {
// pre表示j+1列的黑格
for (int pre = 0; pre <= n; ++pre) {
// dec=1表示j+1列的黑格<j+2列的黑格
for (int dec = 0; dec < 2; ++dec) {
auto& res = f[j + 1][pre][dec];
// cur表示j有多少个黑格子
for (int cur = 0; cur <= n; ++cur) {
if (cur == pre) { //情况1: j = j+1
res = max(res, f[j][cur][0]);
} else if (cur < pre) { //情况2: j < j+1
res = max(res, f[j][cur][1] + col_sum[j][pre] - col_sum[j][cur]);
} else if (!dec) { //情况3: j+1 >= j+2
res = max(res, f[j][cur][0] - col_sum[j + 1][pre] + col_sum[j + 1][cur]);
} else if (pre == 0) { //情况4: j+1 < j+2
res = max(res, f[j][cur][0]);
}
}
}
}
}
// 枚举第 n-1 列有 i 个黑格
ll ans = 0;
for (auto& row : f[n - 1]) {
ans = max(ans, row[0]);
}
return ans;
}
此时，时间复杂度为O(n^3)，空间复杂度为O(n^2)
解法3
时间复杂度太大，把内部cur优化掉。具体如下
long long maximumScore(vector<vector<int>>& grid) {
using ll = long long;
size_t n = grid.size();
// 每列前缀和
vector<vector<ll>> col_sum(n, vector<ll>(n + 1));
for (int j = 0; j < n; ++j) {
for (int i = 0; i < n; ++i) {
col_sum[j][i + 1] = col_sum[j][i] + grid[i][j];
}
}
vector<vector<array<ll, 2>>> f(n, vector<array<ll, 2>>(n + 1));
// 枚举第n-1列有j个黑格
for (int j = 0; j < n - 1; ++j) {
/*
前置概要：
auto& res = f[j + 1][pre][dec];
cur表示j的黑格数，pre表示j+1的黑格数
*/
/*
情况1: cur = pre
因为没有任何意义,f[j+1][cur][state]==f[j][pre][state]
此式可以归纳与情况2
*/
/*
情况2: cur < pre
此时对于原类型中多的归于j，res = max(res, f[j][cur][1] + col_sum[j][pre] - col_sum[j][cur]);
其中需要计算的是res，也就是说在当前情况下col_sum[j][pre]是固定值，则需要维护f[j][cur][1] - col_sum[j][cur]
由于cur小于pre，则需要向前维护一个最大值，即pre_max = max(pre_max, f[j][pre][1] - col_sum[j][pre])
*/
ll pre_max = f[j][0][1] - col_sum[j][0];
for (int pre = 1; pre <= n; ++pre) {
f[j + 1][pre][0] = f[j + 1][pre][1] = max(f[j][pre][0], pre_max + col_sum[j][pre]);
pre_max = max(pre_max, f[j][pre][1] - col_sum[j][pre]);
}
/*
情况3: cur > pre 且 dec == 0
此时同理，维护一个最大值suf_max = max(suf_max, f[j][pre][0] + col_sum[j + 1][pre]);
但cur大于pre，则需要向后维护一个最大值，即suf_max = max(suf_max, f[j][pre][0] + col_sum[j + 1][pre]);
与上述不通的是，由于j+1的大于j+2的，所以赋值默认为f[j][pre][0]
*/
ll suf_max = f[j][n][0] + col_sum[j + 1][n];
for (int pre = n - 1; pre > 0; pre--) {
f[j + 1][pre][0] = max(f[j + 1][pre][0], suf_max - col_sum[j + 1][pre]);
suf_max = max(suf_max, f[j][pre][0] + col_sum[j + 1][pre]);
}
/*
情况4: pre = 0
因为由之前论据来看j+1列一定全白.所以pre=0
f[j + 1][0][0]表示j+1大于等于j+2，但已经是0了所以j+2一定是0。此时f[j][0][0]是不可能的，所以只需要维护不为0时最大值，也就是前面的suf_max
f[j + 1][0][1]说明现在是凹面，理论上来说，f[j + 1][0][1] = max{f[j][0...n-1][1]}，假设j列的是cur个黑块，j-1列是a个黑块
(1)a < cur时，此时分数为cur-a归于a，所以cur越大越好，不如直接n。相当于情况2
(2)a > cur时，pre已经是0了，所以相当于情况3，dec=0，j列的白块都直接做贡献，所以越小越好
因此，f[j+1][0][1] = max(f[j][0][1], f[j][n][1])
*/
f[j + 1][0][0] = suf_max;
f[j + 1][0][1] = max(f[j][0][0], f[j][n][0]);
}
// 枚举第 n-1 列有 i 个黑格
ll ans = 0;
for (auto& row : f[n - 1]) {
ans = max(ans, row[0]);
}
return ans;
}
此时，时间复杂度为O(n^2)，空间复杂度为O(n^2)