个人网站做微擎,包装公司logo设计,泰安百度推广代理商,外贸soho建站本文涉及知识点
动态规划汇总 状态机dp
LeetCode100290. 使矩阵满足条件的最少操作次数
给你一个大小为 m x n 的二维矩形 grid 。每次 操作 中#xff0c;你可以将 任一 格子的值修改为 任意 非负整数。完成所有操作后#xff0c;你需要确保每个格子 grid[i][j] 的值满足…本文涉及知识点
动态规划汇总 状态机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]如果x0或x9则cnt[x]一定为0。故将x换成y(y ∈ \in ∈[0,9])操作次数只会减少或不变。 如果某个最优解第col列小于0或大于9。则换成[0,9]之内和col-1列col1列不同的数。
动态规划
动态规划的状态表示
pre[iPre]表示处理完前c列以iPre结束的最少操作次数。 dp[cur]表示处理完前c1列以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(nm10 × \times ×m × \times × 10)
动态规划的初始值
pre全为0。
动态规划的填表顺序
从第0列到最后一列。
动态规划的返回值
pre的最小值。
代码
templateclass ELE,class ELE2
void MinSelf(ELE* seft, const ELE2 other)
{*seft min(*seft,(ELE) other);
}templateclass ELE
void MaxSelf(ELE* seft, const ELE other)
{*seft max(*seft, other);
}class Solution {
public:int minimumOperations(vectorvectorint grid) {m_r grid.size();m_c grid[0].size();vectorint 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]];}vectorint dp(10,2000000);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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
