发表于 2024.08.31

• 动态规划题目，使用dp[i][j]表示将第i列都改为数字j后，前i列满足条件的最少操作次数。那么状态转移方程为：dp[i][j] = min(dp[i-1][k] + m - cnt[i][j])，其中k枚举前一列可能的数字(且需要k != i)，m表示矩阵的行数，cnt[i][j]表示第i列数字j的个数。为了节省空间，我们可以使用滚动数组优化空间复杂度。

  class Solution {
  public:
      static constexpr int MAX_VAL = 1e9;
      int minimumOperations(vector<vector<int>>& grid) {
          vector<int> dp(10, 0);
          int m = grid.size(), n = grid[0].size();
          for (int i = 0; i < n; ++i) {
              int cnt[10] {};  // 记录第i列每个数字出现的次数
              vector<int> new_dp(10, 0);  // 新的dp数组
              for (int j = 0; j < m; ++j) cnt[grid[j][i]] += 1;
  
              for (int d = 0; d <= 9; ++d) {  // 枚举第i列的每个数字
                  int prev_min_val = MAX_VAL;
                  // 枚举前一列的每个数字
                  for (int pd = 0; pd <= 9; ++pd) if (pd != d) prev_min_val = min(prev_min_val, dp[pd]);
                  new_dp[d] = prev_min_val + (m - cnt[d]);
              }
              dp = std::move(new_dp);
          }
          return *min_element(dp.begin(), dp.end());
      }
  };

• LC 题目链接