【状态机dp 动态规划】100290. 使矩阵满足条件的最少操作次数

本文涉及知识点

动态规划汇总

状态机dp

LeetCode100290. 使矩阵满足条件的最少操作次数

给你一个大小为 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

原理

本题    ⟺    \iff⟺ 各列相同，相邻列不等。

操作后，一定存在最优解，各列的值全部∈ \in∈[0,9]。

将某列全部变成x，需要的操作次数 n - cnt[x]，如果x<0或x>9，则cnt[x]一定为0。故将x换成y(y∈ \in∈[0,9])，操作次数只会减少或不变。

如果某个最优解第col列小于0或大于9。则换成[0,9]之内和col-1列，col+1列不同的数。

动态规划

动态规划的状态表示

pre[iPre]表示处理完前c列，以iPre结束的最少操作次数。

dp[cur]表示处理完前c+1列，以cur结束的最少操作次数。

空间复杂度：O(10)

动态规划的转移方程

动态规划的初始值

pre全为0。

动态规划的填表顺序

从第0列到最后一列。

动态规划的返回值

pre的最小值。

代码

template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
  *seft = min(*seft,(ELE) other);
}
template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
  *seft = max(*seft, other);
}
class Solution {
public:
    int minimumOperations(vector<vector<int>>& grid) {
        m_r = grid.size();
        m_c = grid[0].size();
        vector<int> pre(10);
        for (int c = 0; c < m_c; c++) {
            int cnt[10] = { 0 };
            for (int r = 0; r < m_r; r++) {
                cnt[grid[r][c]]++;
            }
            vector<int> dp(10,2'000'000);
            for (int iPre = 0; iPre < 10; iPre++) {
                for (int cur = 0; cur < 10; cur++) {
                    if (iPre == cur) { continue; }
                    MinSelf(&dp[cur], pre[iPre] + m_r - cnt[cur]);
                }
            }
            pre.swap(dp);
        }
        return *std::min_element(pre.begin(), pre.end());
    }
    int m_r, m_c;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。