本文涉及知识点
动态规划汇总
状态机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 ! = c u r 9 p r e [ x ] + n − c n t [ c u r ] \min_{x:0,x!=cur}^9pre[x]+n-cnt[cur] minx:0,x!=cur9pre[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
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。