Leetcode 3218. Minimum Cost for Cutting Cake I

• Leetcode 3218. Minimum Cost for Cutting Cake I
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3218. Minimum Cost for Cutting Cake I

1. 解题思路

这一题的话其实就是一个贪婪算法的问题，其实就是不断地选取cost最大的cutting优先进行切分，就能够获得最少的cost了。

唯一需要注意的是，由于纵向和横向会产生的切割略有不同，因此当两个cost相同时，需要分别看一下那种cost更低，具体的方式我们采用了动态规划的方式，不过其实直接上也行，这里算是偷了个懒。

2. 代码实现

给出python代码实现如下：

class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        horizontalCut = sorted(horizontalCut, reverse=True)
        verticalCut = sorted(verticalCut, reverse=True)
        
        @lru_cache(None)
        def dp(i, j):
            if i == m-1:
                return sum([c * m for c in verticalCut[j:]])
            elif j == n-1:
                return sum([c * n for c in horizontalCut[i:]])
            elif horizontalCut[i] > verticalCut[j]:
                return horizontalCut[i] * (j+1) + dp(i+1, j)
            elif horizontalCut[i] < verticalCut[j]:
                return verticalCut[j] * (i+1) + dp(i, j+1)
            else:
                return min(horizontalCut[i] * (j+1) + dp(i+1, j), verticalCut[j] * (i+1) + dp(i, j+1))
            
        return dp(0, 0)

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