【状态机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)

动态规划的转移方程

dp[cur] = $min_{x:0,x!=cur}^9pre[x]+n-cnt[cur]$
时间复杂度：O(nm+10 $\times$ m $\times$ 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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛