https://leetcode.cn/problems/minimum-number-of-operations-to-satisfy-conditions/description/
正难则反。
暴力的遍历每一修改的情况,0-9;根据前一列的状态进行转移过来,
下面是状态转移方程
f
(
i
,
j
)
=
m
a
x
(
f
(
i
,
j
)
,
f
(
i
+
1
,
k
)
+
c
n
t
(
i
,
k
)
)
k
!
=
j
;
f(i, j) = max(f(i, j),f(i+1, k)+cnt(i, k)) k!=j;
f(i,j)=max(f(i,j),f(i+1,k)+cnt(i,k))k!=j;
c
n
t
(
i
,
j
)
:第
i
列值为
j
的个数;
cnt(i, j):第i列值为j的个数;
cnt(i,j):第i列值为j的个数;
最后直接
n
∗
m
−
m
a
x
(
f
[
0
]
)
n*m-max(f[0])
n∗m−max(f[0]) 。
class Solution {
public:
int minimumOperations(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> cnt(n, vector<int>(10,0));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cnt[j][grid[i][j]]++;
}
}
vector<vector<int>> dp(n, vector<int>(10, 0));
for(int i=n-1;i>=0;i--){
for(int j=0;j<10;j++){
if(i == n-1){
dp[i][j] = cnt[i][j];
}else{
for(int k = 0;k<10;k++){
if(k == j) continue;
dp[i][j] = max(dp[i][j],dp[i+1][k]+cnt[i][j]);
}
}
}
}
return n*m-*max_element(dp[0].begin(), dp[0].end());
}
};