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

https://leetcode.cn/problems/minimum-number-of-operations-to-satisfy-conditions/description/
正难则反。
暴力的遍历每一修改的情况，0-9；根据前一列的状态进行转移过来，
下面是状态转移方程
$$f(i,j)=max(f(i,j),f(i+1,k)+cnt(i,k))k!=j;$$
$$cnt(i,j)：第i列值为j的个数；$$
最后直接$n\ast 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());
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28