<p>There is an <code>m x n</code> cake that needs to be cut into <code>1 x 1</code> pieces.</p>

<p>You are given integers <code>m</code>, <code>n</code>, and two arrays:</p>

<ul>
	<li><code>horizontalCut</code> of size <code>m - 1</code>, where <code>horizontalCut[i]</code> represents the cost to cut along the horizontal line <code>i</code>.</li>
	<li><code>verticalCut</code> of size <code>n - 1</code>, where <code>verticalCut[j]</code> represents the cost to cut along the vertical line <code>j</code>.</li>
</ul>

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

<ol>
	<li>Cut along a horizontal line <code>i</code> at a cost of <code>horizontalCut[i]</code>.</li>
	<li>Cut along a vertical line <code>j</code> at a cost of <code>verticalCut[j]</code>.</li>
</ol>

<p>After the cut, the piece of cake is divided into two distinct pieces.</p>

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

<p>Return the <strong>minimum</strong> total cost to cut the entire cake into <code>1 x 1</code> pieces.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

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

<p><strong>Explanation:</strong></p>

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

<ul>
	<li>Perform a cut on the vertical line 0 with cost 5, current total cost is 5.</li>
	<li>Perform a cut on the horizontal line 0 on <code>3 x 1</code> subgrid with cost 1.</li>
	<li>Perform a cut on the horizontal line 0 on <code>3 x 1</code> subgrid with cost 1.</li>
	<li>Perform a cut on the horizontal line 1 on <code>2 x 1</code> subgrid with cost 3.</li>
	<li>Perform a cut on the horizontal line 1 on <code>2 x 1</code> subgrid with cost 3.</li>
</ul>

<p>The total cost is <code>5 + 1 + 1 + 3 + 3 = 13</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

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

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

<p><strong>Explanation:</strong></p>

<ul>
	<li>Perform a cut on the horizontal line 0 with cost 7.</li>
	<li>Perform a cut on the vertical line 0 on <code>1 x 2</code> subgrid with cost 4.</li>
	<li>Perform a cut on the vertical line 0 on <code>1 x 2</code> subgrid with cost 4.</li>
</ul>

<p>The total cost is <code>7 + 4 + 4 = 15</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= m, n &lt;= 20</code></li>
	<li><code>horizontalCut.length == m - 1</code></li>
	<li><code>verticalCut.length == n - 1</code></li>
	<li><code>1 &lt;= horizontalCut[i], verticalCut[i] &lt;= 10<sup>3</sup></code></li>
</ul>

"""
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.

- Both m and n are small
- The cut cost is a medium number (smaller than 1000)

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.
- Stopping condition: when the cake is of size 1 by 1

Split a grid into 1 by 1 pieces while minimizing the total cost

Thoughts:
- Can this be a greedy algorithm?
    - i.e at every chance, choose the minimum cost cut
    - No: The first example is a counter example. If we choose the h-cut with cost 1, then we have to peform the cost of 5 twice later on, increasing the cost

Example:
m = 2, n = 2, horizontalCut = [7], verticalCut = [4]
Find the minimum cost so that the cake is cut into a 1 by 1 piece
- The Starting grid is a 2 by 2 grid

Choices:
- Can either make a vertical cut, or a horizontal cut
- I don't see an obvious way to choose which one is best
- I also don't see an obvious way to choose exactly which cut to make

vertical 0 -> cost = cost + verticalCut[0], n = 1, m = 2
horizonal 0 -> cost = cost + horizontalCut[0], m = 1, n = 2

Repeat!
"""

class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        @cache
        def minCost_fromGridSize_givenOffset(rows: int, cols: int, row_offset: int, col_offset: int) -> int:
            # Base cases: the grid is a 1 by 1 grid. In this case we are done ane simply return 0
            if rows == 1 and cols == 1:
                return 0

            min_vertical = math.inf
            min_horizontal = math.inf

            # The min cost is the cost to split, plus the cost from the remaining sub-problems
            for row in range(1, rows):
                h_cost = horizontalCut[row-1 + row_offset] + minCost_fromGridSize_givenOffset(row, cols, row_offset, col_offset) + minCost_fromGridSize_givenOffset(rows - row, cols, row_offset + row, col_offset)
                if h_cost < min_horizontal:
                    min_horizontal = h_cost 

            for col in range(1, cols):
                v_cost = verticalCut[col-1 + col_offset] + minCost_fromGridSize_givenOffset(rows, col, row_offset, col_offset) + minCost_fromGridSize_givenOffset(rows, cols - col, row_offset, col_offset + col)
                if v_cost < min_vertical:
                    min_vertical = v_cost 

            return min(min_horizontal, min_vertical) 


        return minCost_fromGridSize_givenOffset(m, n, 0, 0)

550