Leetcode 3122. Minimum Number of Operations to Satisfy Conditions

• Leetcode 3122. Minimum Number of Operations to Satisfy Conditions
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3122. Minimum Number of Operations to Satisfy Conditions

1. 解题思路

这一题就是一个动态规划的思路，我们只需要对每一列取0到9的情况各自进行一下讨论，然后看和当前元素当中重复度最高的一个既是我们目标的情况，将其返回即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        cnt = [[0 for _ in range(m)] for _ in range(10)]
        for i in range(n):
            for j in range(m):
                cnt[grid[i][j]][j] += 1
                
        @lru_cache(None)
        def dp(idx, pre):
            if idx >= m:
                return 0
            ans = 0
            for i in range(10):
                if i == pre:
                    continue
                ans = max(ans, cnt[i][idx] + dp(idx+1, i))
            return ans
        
        return n * m - dp(0, -1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

提交代码评测得到：耗时2431ms，占用内存51.1MB。