lc3219. 切蛋糕的最小总开销 ii

链接： 3219. 切蛋糕的最小总开销 II - 力扣（LeetCode）

题解

贪心半天，最后还是看了题解，只差一层窗户纸，还是要独立自己写。

解题比较关键的一点是，逆向思考，从 n*m 块小蛋糕最终合并成一个大蛋糕。问题变成水平合并 m-1 次，垂直合并 n-1 次。为了结果最小，刚开始应该先合并开销小的。

假设水平当前已经合并到 i，垂直已经合并到 j，分别开销是 horizontalCut[i]*(n-j) 和 verticalCut[j]*(m-i)。

• 自己一直每一步是选择这两个值里面最小的合并，如果两个值相等，就选择两个之间 horizontalCut[i] 和 verticalCut[j]，这样下一步开销会减小的更多。
• 看题解直接是贪心选择 horizontalCut[i] 和 verticalCut[j] 之间最小的即可，这样才是下一步开销减小最多的。

参考代码

class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
    
        horizontalCut.sort()
        verticalCut.sort() 
        cost = 0
        i = 0
        j = 0
        while True:
            if m == 1 and n == 1:
                break
            # print(i, j, m, n)
            if n == 1:
                cost += horizontalCut[i]
                i += 1
                m -= 1
            elif m == 1:
                cost += verticalCut[j]
                j += 1
                n -= 1
            elif horizontalCut[i] < verticalCut[j]:
                cost += horizontalCut[i] * n
                i += 1
                m -= 1
            else:
                cost += verticalCut[j] * m
                j += 1
                n -= 1
            
        return cost