网格图操作后的最大分数

100341. 网格图操作后的最大分数

给你一个大小为 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 <= 100
n == grid[i].length
0 <= grid[i][j] <= 10⁹

相似题目

矩阵中的最大得分

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: long long maximumScore(vector<vector<int>>& grid) { } };

cpp 解法, 执行用时: 53 ms, 内存消耗: 42.1 MB, 提交时间: 2024-07-23 22:09:23

class Solution {
public:
    long long maximumScore(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<long long>> col_sum(n, vector<long long>(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<long long, 2>>> f(n, vector<array<long long, 2>>(n + 1));
        for (int j = 0; j < n - 1; j++) {
            // 用前缀最大值优化
            long long 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]);
            }

            // 用后缀最大值优化
            long long 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]);
            }

            // 单独计算 pre=0 的状态
            f[j + 1][0][0] = suf_max; // 无需考虑 f[j][0][0]，因为不能连续三列全白
            f[j + 1][0][1] = max(f[j][0][0], f[j][n][0]); // 第 j 列要么全白，要么全黑
        }

        long long ans = 0;
        for (auto& row : f[n - 1]) {
            ans = max(ans, row[0]);
        }
        return ans;
    }
};

java 解法, 执行用时: 10 ms, 内存消耗: 44.1 MB, 提交时间: 2024-07-23 22:09:10

class Solution {
    public long maximumScore(int[][] grid) {
        int n = grid.length;
        long[][] colSum = new long[n][n + 1];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                colSum[j][i + 1] = colSum[j][i] + grid[i][j];
            }
        }

        long[][][] f = new long[n][n + 1][2];
        for (int j = 0; j < n - 1; j++) {
            // 用前缀最大值优化
            long preMax = f[j][0][1] - colSum[j][0];
            for (int pre = 1; pre <= n; pre++) {
                f[j + 1][pre][0] = f[j + 1][pre][1] = Math.max(f[j][pre][0], preMax + colSum[j][pre]);
                preMax = Math.max(preMax, f[j][pre][1] - colSum[j][pre]);
            }

            // 用后缀最大值优化
            long sufMax = f[j][n][0] + colSum[j + 1][n];
            for (int pre = n - 1; pre > 0; pre--) {
                f[j + 1][pre][0] = Math.max(f[j + 1][pre][0], sufMax - colSum[j + 1][pre]);
                sufMax = Math.max(sufMax, f[j][pre][0] + colSum[j + 1][pre]);
            }

            // 单独计算 pre=0 的状态
            f[j + 1][0][0] = sufMax; // 无需考虑 f[j][0][0]，因为不能连续三列全白
            f[j + 1][0][1] = Math.max(f[j][0][0], f[j][n][0]); // 第 j 列要么全白，要么全黑
        }

        long ans = 0;
        for (long[] row : f[n - 1]) {
            ans = Math.max(ans, row[0]);
        }
        return ans;
    }
}

golang 解法, 执行用时: 25 ms, 内存消耗: 7.1 MB, 提交时间: 2024-07-23 22:08:56

func maximumScore(grid [][]int) (ans int64) {
	n := len(grid)
	colSum := make([][]int64, n)
	for j := range colSum {
		colSum[j] = make([]int64, n+1)
		for i, row := range grid {
			colSum[j][i+1] = colSum[j][i] + int64(row[j])
		}
	}

	f := make([][][2]int64, n)
	for j := range f {
		f[j] = make([][2]int64, n+1)
	}
	for j := 0; j < n-1; j++ {
		// 用前缀最大值优化
		preMax := f[j][0][1] - colSum[j][0]
		for pre := 1; pre <= n; pre++ {
			f[j+1][pre][0] = max(f[j][pre][0], preMax+colSum[j][pre])
			f[j+1][pre][1] = f[j+1][pre][0]
			preMax = max(preMax, f[j][pre][1]-colSum[j][pre])
		}

		// 用后缀最大值优化
		sufMax := f[j][n][0] + colSum[j+1][n]
		for pre := n - 1; pre > 0; pre-- {
			f[j+1][pre][0] = max(f[j+1][pre][0], sufMax-colSum[j+1][pre])
			sufMax = max(sufMax, f[j][pre][0]+colSum[j+1][pre])
		}

		// 单独计算 pre=0 的状态
		f[j+1][0][0] = sufMax // 无需考虑 f[j][0][0]，因为不能连续三列全白
		f[j+1][0][1] = max(f[j][0][0], f[j][n][0]) // 第 j 列要么全白，要么全黑
	}

	for _, row := range f[n-1] {
		ans = max(ans, row[0])
	}
	return ans
}

python3 解法, 执行用时: 179 ms, 内存消耗: 19.4 MB, 提交时间: 2024-07-23 22:08:36

class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        col_sum = [list(accumulate(col, initial=0)) for col in zip(*grid)]

        f = [[[0, 0] for _ in range(n + 1)] for _ in range(n)]
        for j in range(n - 1):
            # 用前缀最大值优化
            pre_max = f[j][0][1] - col_sum[j][0]
            for pre in range(1, n + 1):
                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])

            # 用后缀最大值优化
            suf_max = f[j][n][0] + col_sum[j + 1][n]
            for pre in range(n - 1, 0, -1):
                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])

            # 单独计算 pre=0 的状态
            f[j + 1][0][0] = suf_max  # 无需考虑 f[j][0][0]，因为不能连续三列全白
            f[j + 1][0][1] = max(f[j][0][0], f[j][n][0])  # 第 j 列要么全白，要么全黑

        return max(f[-1][i][0] for i in range(n + 1))

python3 解法, 执行用时: 3741 ms, 内存消耗: 19.5 MB, 提交时间: 2024-07-23 22:08:25

class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        # 每列的前缀和（从上到下）
        col_sum = [list(accumulate(col, initial=0)) for col in zip(*grid)]
        f = [[[0, 0] for _ in range(n + 1)] for _ in range(n)]
        for j in range(n - 1):
            # pre 表示第 j+1 列的黑格个数
            for pre in range(n + 1):
                # dec=1 意味着第 j+1 列的黑格个数 (pre) < 第 j+2 列的黑格个数
                for dec in range(2):
                    res = 0
                    # 枚举第 j 列有 cur 个黑格
                    for cur in range(n + 1):
                        if cur == pre:  # 情况一：相等
                            # 没有可以计入总分的格子
                            res = max(res, f[j][cur][0])
                        elif cur < pre:  # 情况二：右边黑格多
                            # 第 j 列的第 [cur, pre) 行的格子可以计入总分
                            res = max(res, f[j][cur][1] + col_sum[j][pre] - col_sum[j][cur])
                        elif dec == 0:  # 情况三：cur > pre >= 第 j+2 列的黑格个数
                            # 第 j+1 列的第 [pre, cur) 行的格子可以计入总分
                            res = max(res, f[j][cur][0] + col_sum[j + 1][cur] - col_sum[j + 1][pre])
                        elif pre == 0:  # 情况四（凹形）：cur > pre < 第 j+2 列的黑格个数
                            # 此时第 j+2 列全黑最优（递归过程中一定可以枚举到这种情况）
                            # 第 j+1 列全白是最优的，所以只需考虑 pre=0 的情况
                            # 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过，这里不重复统计
                            res = max(res, f[j][cur][0])
                    f[j + 1][pre][dec] = res
        # 枚举第 n-1 列有 i 个黑格
        return max(f[-1][i][0] for i in range(n + 1))

python3 解法, 执行用时: 5431 ms, 内存消耗: 51.4 MB, 提交时间: 2024-07-23 22:08:13

class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        # 每列的前缀和（从上到下）
        col_sum = [list(accumulate(col, initial=0)) for col in zip(*grid)]

        # pre 表示第 j+1 列的黑格个数
        # dec=True 意味着第 j+1 列的黑格个数 (pre) < 第 j+2 列的黑格个数
        @cache
        def dfs(j: int, pre: int, dec: bool) -> int:
            if j < 0:
                return 0
            res = 0
            # 枚举第 j 列有 cur 个黑格
            for cur in range(n + 1):
                if cur == pre:  # 情况一：相等
                    # 没有可以计入总分的格子
                    res = max(res, dfs(j - 1, cur, False))
                elif cur < pre:  # 情况二：右边黑格多
                    # 第 j 列的第 [cur, pre) 行的格子可以计入总分
                    res = max(res, dfs(j - 1, cur, True) + col_sum[j][pre] - col_sum[j][cur])
                elif not dec:  # 情况三：cur > pre >= 第 j+2 列的黑格个数
                    # 第 j+1 列的第 [pre, cur) 行的格子可以计入总分
                    res = max(res, dfs(j - 1, cur, False) + col_sum[j + 1][cur] - col_sum[j + 1][pre])
                elif pre == 0:  # 情况四（凹形）：cur > pre < 第 j+2 列的黑格个数
                    # 此时第 j+2 列全黑最优（递归过程中一定可以枚举到这种情况）
                    # 第 j+1 列全白是最优的，所以只需考虑 pre=0 的情况
                    # 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过，这里不重复统计
                    res = max(res, dfs(j - 1, cur, False))
            return res
        # 枚举第 n-1 列有 i 个黑格
        return max(dfs(n - 2, i, False) for i in range(n + 1))

上一题

下一题

详情