Hard

题目描述

给定一个大小为 n x n 的二维矩阵 grid。最初，网格的所有单元格都是白色的。在一次操作中，你可以选择任意位置为 (i, j) 的单元格，并将第 j 列从顶行到第 i 行的所有单元格涂成黑色。

网格分数是所有 grid[i][j] 的和，其中单元格 (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^9

解题思路

这道题的核心是理解分数计算规则：只有白色格子且有相邻黑色格子的位置才计入分数。

问题分析：

  1. 每列可以选择一个高度进行涂黑（从顶部开始）
  2. 白色格子的左右相邻有黑色格子时才能得分
  3. 需要找到最优的每列涂黑高度组合

动态规划思路： 使用三维DP：dp[col][height][isBigger] 表示：

  • 处理到第 col 列
  • 第 col-1 列的涂黑高度为 height
  • isBigger 表示第 col 列的高度是否大于第 col-2 列

状态转移：

  1. 遍历每列的所有可能高度
  2. 计算当前列对分数的贡献
  3. 根据相邻列的高度关系更新状态

分数计算细节：

  • 如果当前列高度 > 前一列高度，前一列的某些白色格子可以得分
  • 如果当前列高度 < 前一列高度，当前列的某些白色格子可以得分

这个方法时间复杂度为 O(n⁴)，符合题目提示的要求。

代码实现

class Solution {
public:
    long long maximumScore(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<long long>> prefix(n, vector<long long>(n + 1, 0));
        
        // 计算前缀和
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                prefix[j][i + 1] = prefix[j][i] + grid[i][j];
            }
        }
        
        // dp[col][height][isBigger]
        vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(n + 1, vector<long long>(2, LLONG_MIN)));
        dp[0][0][0] = dp[0][0][1] = 0;
        
        for (int col = 1; col <= n; col++) {
            for (int h = 0; h <= n; h++) {
                for (int prevH = 0; prevH <= n; prevH++) {
                    for (int prevIsBigger = 0; prevIsBigger < 2; prevIsBigger++) {
                        if (dp[col - 1][prevH][prevIsBigger] == LLONG_MIN) continue;
                        
                        long long score = dp[col - 1][prevH][prevIsBigger];
                        
                        // 计算当前配置下的得分
                        if (col >= 2) {
                            bool actuallyBigger = (col == 2) ? (prevH > 0) : (prevIsBigger == 1);
                            if (actuallyBigger) {
                                // 前一列比前前一列高，前一列的一些白色格子得分
                                if (h < prevH) {
                                    score += prefix[col - 2][prevH] - prefix[col - 2][h];
                                }
                            } else {
                                // 前一列不比前前一列高，当前列的一些白色格子得分
                                if (h > prevH) {
                                    score += prefix[col - 2][h] - prefix[col - 2][prevH];
                                }
                            }
                        }
                        
                        // 确定新的 isBigger 状态
                        int newIsBigger = (h > prevH) ? 1 : 0;
                        dp[col][h][newIsBigger] = max(dp[col][h][newIsBigger], score);
                    }
                }
            }
        }
        
        long long result = 0;
        for (int h = 0; h <= n; h++) {
            for (int isBigger = 0; isBigger < 2; isBigger++) {
                if (dp[n][h][isBigger] != LLONG_MIN) {
                    long long score = dp[n][h][isBigger];
                    // 添加最后一列的贡献
                    if (n >= 2) {
                        if (isBigger == 1) {
                            // 最后一列比倒数第二列高，最后一列的一些白色格子得分
                            score += prefix[n - 1][n] - prefix[n - 1][h];
                        }
                    }
                    result = max(result, score);
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        
        # 计算前缀和
        prefix = [[0] * (n + 1) for _ in range(n)]
        for j in range(n):
            for i in range(n):
                prefix[j][i + 1] = prefix[j][i] + grid[i][j]
        
        # dp[col][height][isBigger]
        dp = [[[-float('inf')] * 2 for _ in range(n + 1)] for _ in range(n + 1)]
        dp[0][0][0] = dp[0][0][1] = 0
        
        for col in range(1, n + 1):
            for h in range(n + 1):
                for prev_h in range(n + 1):
                    for prev_is_bigger in range(2):
                        if dp[col - 1][prev_h][prev_is_bigger] == -float('inf'):
                            continue
                        
                        score = dp[col - 1][prev_h][prev_is_bigger]
                        
                        # 计算当前配置下的得分
                        if col >= 2:
                            actually_bigger = (prev_h > 0) if col == 2 else (prev_is_bigger == 1)
                            if actually_bigger:
                                # 前一列比前前一列高
                                if h < prev_h:
                                    score += prefix[col - 2][prev_h] - prefix[col - 2][h]
                            else:
                                # 前一列不比前前一列高
                                if h > prev_h:
                                    score += prefix[col - 2][h] - prefix[col - 2][prev_h]
                        
                        # 确定新的 isBigger 状态
                        new_is_bigger = 1 if h > prev_h else 0
                        dp[col][h][new_is_bigger] = max(dp[col][h][new_is_bigger], score)
        
        result = 0
        for h in range(n + 1):
            for is_bigger in range(2):
                if dp[n][h][is_bigger] != -float('inf'):
                    score = dp[n][h][is_bigger]
                    # 添加最后一列的贡献
                    if n >= 2:
                        if is_bigger == 1:
                            score += prefix[n - 1][n] - prefix[n - 1][h]
                    result = max(result, score)
        
        return result

public class Solution {
    public long MaximumScore(int[][] grid) {
        int n = grid.Length;
        long[,] prefix = new long[n, n + 1];
        
        // 计算前缀和
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                prefix[j, i + 1] = prefix[j, i] + grid[i][j];
            }
        }
        
        // dp[col][height][isBigger]
        long[,,] dp = new long[n + 1, n + 1, 2];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k < 2; k++) {
                    dp[i, j, k] = long.MinValue;
                }
            }
        }
        dp[0, 0, 0] = dp[0, 0, 1] = 0;
        
        for (int col = 1; col <= n; col++) {
            for (int h = 0; h <= n; h++) {
                for (int prevH = 0; prevH <= n; prevH++) {
                    for (int prevIsBigger = 0; prevIsBigger < 2; prevIsBigger++) {
                        if (dp[col - 1, prevH, prevIsBigger] == long.MinValue) continue;
                        
                        long score = dp[col - 1, prevH, prevIsBigger];
                        
                        // 计算当前配置下的得分
                        if (col >= 2) {
                            bool actuallyBigger = (col == 2) ? (prevH > 0) : (prevIsBigger == 1);
                            if (actuallyBigger) {
                                if (h < prevH) {
                                    score += prefix[col - 2, prevH] - prefix[col - 2, h];
                                }
                            } else {
                                if (h > prevH) {
                                    score += prefix[col - 2, h] - prefix[col - 2, prevH];
                                }
                            }
                        }
                        
                        int newIsBigger = (h > prevH) ? 1 : 0;
                        dp[col, h, newIsBigger] = Math.Max(dp[col, h, newIsBigger], score);
                    }
                }
            }
        }
        
        long result = 0;
        for (int h = 0; h <= n; h++) {
            for (int isBigger = 0; isBigger < 2; isBigger++) {
                if (dp[n, h, isBigger] != long.MinValue) {
                    long score = dp[n, h, isBigger];
                    if (n >= 2 && isBigger == 1) {
                        score += prefix[n - 1, n] - prefix[n - 1, h];
                    }
                    result = Math.Max(result, score);
                }
            }
        }
        
        return result;
    }
}

var maximumScore = function(grid) {
    const n = grid.length;
    const memo = new Map();
    
    function dp(col, heights) {
        if (col === n) return 0;
        
        const key = col + ',' + heights.join(',');
        if (memo.has(key)) return memo.get(key);
        
        let maxScore = 0;
        
        // Try all possible heights for current column (0 to n)
        for (let h = 0; h <= n; h++) {
            let score = 0;
            
            // Calculate score for current configuration
            for (let c = 0; c < n; c++) {
                const prevHeight = c === col ? h : heights[c];
                
                for (let r = 0; r < n; r++) {
                    const isBlack = r < prevHeight;
                    
                    if (!isBlack) {
                        // Check left neighbor
                        if (c > 0) {
                            const leftHeight = c === 1 && col === 0 ? h : heights[c - 1];
                            if (r < leftHeight) {
                                score += grid[r][c];
                            }
                        }
                        
                        // Check right neighbor
                        if (c < n - 1) {
                            const rightHeight = c === n - 2 && col === n - 1 ? h : 
                                              (col === c + 1 ? h : heights[c + 1]);
                            if (col > c + 1 && r < rightHeight) {
                                score += grid[r][c];
                            } else if (col === c + 1 && r < h) {
                                score += grid[r][c];
                            }
                        }
                    }
                }
            }
            
            const newHeights = [...heights];
            newHeights[col] = h;
            maxScore = Math.max(maxScore, score + dp(col + 1, newHeights));
        }
        
        memo.set(key, maxScore);
        return maxScore;
    }
    
    // Simpler approach: try all combinations
    const memo2 = new Map();
    
    function solve(col, config) {
        if (col === n) {
            return calculateScore(config);
        }
        
        const key = col + ',' + config.join(',');
        if (memo2.has(key)) return memo2.get(key);
        
        let maxScore = 0;
        for (let h = 0; h <= n; h++) {
            const newConfig = [...config];
            newConfig[col] = h;
            maxScore = Math.max(maxScore, solve(col + 1, newConfig));
        }
        
        memo2.set(key, maxScore);
        return maxScore;
    }
    
    function calculateScore(heights) {
        let score = 0;
        
        for (let r = 0; r < n; r++) {
            for (let c = 0; c < n; c++) {
                const isBlack = r < heights[c];
                
                if (!isBlack) {
                    // Check if has adjacent black cell
                    let hasBlackNeighbor = false;
                    
                    // Left neighbor
                    if (c > 0 && r < heights[c - 1]) {
                        hasBlackNeighbor = true;
                    }
                    
                    // Right neighbor
                    if (c < n - 1 && r < heights[c + 1]) {
                        hasBlackNeighbor = true;
                    }
                    
                    if (hasBlackNeighbor) {
                        score += grid[r][c];
                    }
                }
            }
        }
        
        return score;
    }
    
    return solve(0, new Array(n).fill(0));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-

相关题目