Medium

题目描述

给你一个大小为 m x n 的二维矩阵 grid。在一次操作中，你可以将任意一个单元格的值更改为任意非负数。你需要执行一些操作，使得每个单元格 grid[i][j] 满足：

  • 等于其下方的单元格，即 grid[i][j] == grid[i + 1][j]（如果存在）。
  • 不等于其右侧的单元格，即 grid[i][j] != grid[i][j + 1]（如果存在）。

返回所需的最小操作数。

示例 1：

输入：grid = [[1,0,2],[1,0,2]]
输出：0
解释：
矩阵中的所有单元格已经满足性质。

示例 2：

输入：grid = [[1,1,1],[0,0,0]]
输出：3
解释：
矩阵变为 [[1,0,1],[1,0,1]]，满足性质，需要进行 3 次操作：
- 将 grid[1][0] 改为 1。
- 将 grid[0][1] 改为 0。
- 将 grid[1][2] 改为 1。

示例 3：

输入：grid = [[1],[2],[3]]
输出：2
解释：
只有一列。我们可以使用 2 次操作将每个单元格的值都改为 1。

提示：

  • 1 <= n, m <= 1000
  • 0 <= grid[i][j] <= 9

解题思路

这是一个动态规划问题，关键在于理解题目的约束条件：

  1. 同一列中相邻的单元格必须相同
  2. 同一行中相邻的单元格必须不同

思路分析：

由于同一列中所有单元格必须相同，我们可以将问题转化为：对每一列选择一个值（0-9），使得相邻列的值不同，且总的修改成本最小。

解题步骤：

  1. 预处理：对于每一列，统计将其全部改为某个值（0-9）需要的操作次数
  2. 动态规划：定义 dp[j][val] 表示处理前 j 列，且第 j 列选择值 val 时的最小操作数
  3. 状态转移：对于第 j 列选择值 val，它可以从第 j-1 列的任意不等于 val 的值转移而来
  4. 优化：维护前一列的最小值和次小值，避免重复计算

时间复杂度优化：

  • 朴素动态规划：O(n × 10²)
  • 优化后：O(n × 10)，通过维护最小值和次小值来优化转移过程

这种方法的核心思想是将二维问题转化为一维问题，通过列的角度来思考，大大简化了问题的复杂度。

代码实现

class Solution {
public:
    int minimumOperations(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 预处理：计算每列改为每个值的成本
        vector<vector<int>> cost(n, vector<int>(10, 0));
        for (int j = 0; j < n; j++) {
            for (int val = 0; val < 10; val++) {
                for (int i = 0; i < m; i++) {
                    if (grid[i][j] != val) {
                        cost[j][val]++;
                    }
                }
            }
        }
        
        // dp[val] 表示当前列选择值val的最小成本
        vector<int> dp(10, INT_MAX);
        
        // 初始化第一列
        for (int val = 0; val < 10; val++) {
            dp[val] = cost[0][val];
        }
        
        // 处理后续列
        for (int j = 1; j < n; j++) {
            vector<int> newDp(10, INT_MAX);
            
            // 找到当前dp的最小值和次小值
            int minVal = 0, secondMinVal = 1;
            if (dp[1] < dp[0]) {
                minVal = 1;
                secondMinVal = 0;
            }
            for (int val = 2; val < 10; val++) {
                if (dp[val] < dp[minVal]) {
                    secondMinVal = minVal;
                    minVal = val;
                } else if (dp[val] < dp[secondMinVal]) {
                    secondMinVal = val;
                }
            }
            
            // 状态转移
            for (int val = 0; val < 10; val++) {
                int prevCost = (val == minVal) ? dp[secondMinVal] : dp[minVal];
                newDp[val] = prevCost + cost[j][val];
            }
            
            dp = newDp;
        }
        
        return *min_element(dp.begin(), dp.end());
    }
};

class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 预处理：计算每列改为每个值的成本
        cost = [[0] * 10 for _ in range(n)]
        for j in range(n):
            for val in range(10):
                for i in range(m):
                    if grid[i][j] != val:
                        cost[j][val] += 1
        
        # dp[val] 表示当前列选择值val的最小成本
        dp = [cost[0][val] for val in range(10)]
        
        # 处理后续列
        for j in range(1, n):
            new_dp = [float('inf')] * 10
            
            # 找到当前dp的最小值和次小值
            sorted_vals = sorted(range(10), key=lambda x: dp[x])
            min_val, second_min_val = sorted_vals[0], sorted_vals[1]
            
            # 状态转移
            for val in range(10):
                prev_cost = dp[second_min_val] if val == min_val else dp[min_val]
                new_dp[val] = prev_cost + cost[j][val]
            
            dp = new_dp
        
        return min(dp)

public class Solution {
    public int MinimumOperations(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        // 预处理：计算每列改为每个值的成本
        int[,] cost = new int[n, 10];
        for (int j = 0; j < n; j++) {
            for (int val = 0; val < 10; val++) {
                for (int i = 0; i < m; i++) {
                    if (grid[i][j] != val) {
                        cost[j, val]++;
                    }
                }
            }
        }
        
        // dp[val] 表示当前列选择值val的最小成本
        int[] dp = new int[10];
        for (int val = 0; val < 10; val++) {
            dp[val] = cost[0, val];
        }
        
        // 处理后续列
        for (int j = 1; j < n; j++) {
            int[] newDp = new int[10];
            Array.Fill(newDp, int.MaxValue);
            
            // 找到当前dp的最小值和次小值
            int minVal = 0, secondMinVal = 1;
            if (dp[1] < dp[0]) {
                minVal = 1;
                secondMinVal = 0;
            }
            for (int val = 2; val < 10; val++) {
                if (dp[val] < dp[minVal]) {
                    secondMinVal = minVal;
                    minVal = val;
                } else if (dp[val] < dp[secondMinVal]) {
                    secondMinVal = val;
                }
            }
            
            // 状态转移
            for (int val = 0; val < 10; val++) {
                int prevCost = (val == minVal) ? dp[secondMinVal] : dp[minVal];
                newDp[val] = prevCost + cost[j, val];
            }
            
            dp = newDp;
        }
        
        return dp.Min();
    }
}

var minimumOperations = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    // For each column, count frequency of each digit (0-9)
    const colFreq = [];
    for (let j = 0; j < n; j++) {
        const freq = new Array(10).fill(0);
        for (let i = 0; i < m; i++) {
            freq[grid[i][j]]++;
        }
        colFreq.push(freq);
    }
    
    // dp[j][digit] = min operations for columns 0 to j where column j uses digit
    const dp = Array(n).fill(null).map(() => new Array(10).fill(Infinity));
    
    // Initialize first column
    for (let digit = 0; digit < 10; digit++) {
        dp[0][digit] = m - colFreq[0][digit];
    }
    
    // Fill dp table
    for (let j = 1; j < n; j++) {
        for (let digit = 0; digit < 10; digit++) {
            const cost = m - colFreq[j][digit];
            for (let prevDigit = 0; prevDigit < 10; prevDigit++) {
                if (prevDigit !== digit) {
                    dp[j][digit] = Math.min(dp[j][digit], dp[j-1][prevDigit] + cost);
                }
            }
        }
    }
    
    return Math.min(...dp[n-1]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n × 10)预处理需要 O(m × n × 10)，动态规划需要 O(n × 10)
空间复杂度O(n × 10)存储每列的成本数组和动态规划数组

相关题目