Skip to content

Latest commit

 

History

History
109 lines (61 loc) · 2.62 KB

3218-minimum-cost-for-cutting-cake-i.adoc

File metadata and controls

109 lines (61 loc) · 2.62 KB

3218. Minimum Cost for Cutting Cake I

{leetcode}/problems/minimum-cost-for-cutting-cake-i/[LeetCode - 3218. Minimum Cost for Cutting Cake I ^]

There is an m x n cake that needs to be cut into 1 x 1 pieces.

You are given integers m, n, and two arrays:

  • horizontalCut of size m - 1, where horizontalCut[i] represents the cost to cut along the horizontal line i.

  • verticalCut of size n - 1, where verticalCut[j] represents the cost to cut along the vertical line j.

In one operation, you can choose any piece of cake that is not yet a 1 x 1 square and perform one of the following cuts:

  • Cut along a horizontal line i at a cost of horizontalCut[i].

  • Cut along a vertical line j at a cost of verticalCut[j].

After the cut, the piece of cake is divided into two distinct pieces.

The cost of a cut depends only on the initial cost of the line and does not change.

Return the minimum total cost to cut the entire cake into 1 x 1 pieces.

Example 1:

<div class="example-block"> Input: <span class="example-io">m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]

Output: <span class="example-io">13

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/06/04/ezgifcom-animated-gif-maker-1.gif" style="width: 280px; height: 320px;" />

  • Perform a cut on the vertical line 0 with cost 5, current total cost is 5.

  • Perform a cut on the horizontal line 0 on 3 x 1 subgrid with cost 1.

  • Perform a cut on the horizontal line 0 on 3 x 1 subgrid with cost 1.

  • Perform a cut on the horizontal line 1 on 2 x 1 subgrid with cost 3.

  • Perform a cut on the horizontal line 1 on 2 x 1 subgrid with cost 3.

The total cost is 5 + 1 + 1 + 3 + 3 = 13.

Example 2:

<div class="example-block"> Input: <span class="example-io">m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

Output: <span class="example-io">15

Explanation:

  • Perform a cut on the horizontal line 0 with cost 7.

  • Perform a cut on the vertical line 0 on 1 x 2 subgrid with cost 4.

  • Perform a cut on the vertical line 0 on 1 x 2 subgrid with cost 4.

The total cost is 7 + 4 + 4 = 15.

Constraints:

  • 1 ⇐ m, n ⇐ 20

  • horizontalCut.length == m - 1

  • verticalCut.length == n - 1

  • 1 ⇐ horizontalCut[i], verticalCut[i] ⇐ 103

思路分析

一刷
link:{sourcedir}/_3218_MinimumCostForCuttingCakeI.java[role=include]

参考资料