JZX轻语：简
LeetCode 3122 - 使矩阵满足条件的最少操作次数
发表于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());
}
};