Leetcode 3257. Maximum Value Sum by Placing Three Rooks II

• Leetcode 3257. Maximum Value Sum by Placing Three Rooks II
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3257. Maximum Value Sum by Placing Three Rooks II

1. 解题思路

这道题同样是题目3256的一个进阶版本，但同样也只是增加了复杂度而已，整体而言两者的解题思路是完全相同的，就是一个遍历+剪枝的思路。

首先，我们将所有元素按照其值的大小从大到小进行排列，然后依次考察每个元素被选入的情况，这个就是一个简单的迭代算法，倒是也没啥复杂的。

但是显然，如果不加上任何额外操作，整体的算法复杂度就会是$O(n^3{m}^3)$，这显然是不可接受的，因此我们需要进行剪枝，而剪枝逻辑倒也简单，我们优先从大到小进行选取，如果后续连续元素加上之前已选的元素的和已经无法超过当前选到的最大值了，那么后续所有的遍历都没必要再进行了，此时我们就能大幅缩减整体的算法复杂度，使之通过这两道题的全部测试样例。

2. 代码实现

给出python代码实现如下：

class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        n, m = len(board), len(board[0])
        ans = -math.inf
        cells = [(board[i][j], i, j) for i in range(n) for j in range(m)]
        cells = sorted(cells, reverse=True)
        N = n * m
        
        def dfs(idx, selected, pre):
            nonlocal ans
            if len(selected) == 3:
                ans = max(ans, pre)
            if idx >= N:
                return
            if pre + sum(x[0] for x in cells[idx: idx+3-len(selected)]) <= ans:
                return
            if selected == [] or all(cells[idx][1] != x and cells[idx][2] != y for x, y in selected):
                dfs(idx+1, selected + [(cells[idx][1], cells[idx][2])], pre + cells[idx][0])
            dfs(idx+1, selected, pre)
            return
        
        dfs(0, [], 0)
        return ans

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