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

class Solution:
    def minimumCost2(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int], horizontalStart: int, horizontalEnd: int, verticalStart: int, verticalEnd: int, visited: Dict[str, int]) -> int:
        minimumCost: int = 999999999

        if (horizontalStart == horizontalEnd) and (verticalStart == verticalEnd):
            return 0

        hash: str = f'{horizontalStart}_{horizontalEnd}_{verticalStart}_{verticalEnd}'

        if hash in visited.keys():
            return visited[hash]

        cost: int = 0
        for i in range(horizontalStart, horizontalEnd):
            cost = self.minimumCost2(m, n, horizontalCut, verticalCut, horizontalStart, i, verticalStart, verticalEnd, visited) + self.minimumCost2(m, n, horizontalCut, verticalCut, i + 1, horizontalEnd, verticalStart, verticalEnd, visited) + horizontalCut[i]

            if cost < minimumCost:
                minimumCost = cost

        for j in range(verticalStart, verticalEnd):
            cost = self.minimumCost2(m, n, horizontalCut, verticalCut, horizontalStart, horizontalEnd, verticalStart, j, visited) + self.minimumCost2(m, n, horizontalCut, verticalCut, horizontalStart, horizontalEnd, j + 1, verticalEnd, visited) + verticalCut[j]

            if cost < minimumCost:
                minimumCost = cost            

        visited[hash] = minimumCost
        return minimumCost

    # def g(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int], horizontalStart: int, horizontalEnd: int, verticalStart: int, verticalEnd: int, visited: Dict[str, int]) -> int:
        print((horizontalStart, horizontalEnd, verticalStart, verticalEnd))

        if (horizontalStart == horizontalEnd - 1) and (verticalStart == verticalEnd - 1):
            return 0

        # hash: str = f'{horizontalStart}_{horizontalEnd}_{verticalStart}_{verticalEnd}'

        # if hash in visited.keys():
        #     return visited[hash]

        hmaxFound: bool = False
        vmaxFound: bool = False
        hmaxval: int = 999999
        vmaxval: int = 999999

        hmax: int = 0
        vmax:int = 0

        for i in range(horizontalStart, horizontalEnd):
            if hmaxFound == False:
                hmaxFound = True
                hmax = i
                hmaxval = horizontalCut[hmax]
            else:
                if horizontalCut[i] > horizontalCut[hmax]:
                    hmax = i
                    hmaxval = horizontalCut[hmax]

        for i in range(verticalStart, verticalEnd):
            if vmaxFound == False:
                vmaxFound = True
                vmax = i
                vmaxval = verticalCut[vmax]
            else:
                if verticalCut[i] > verticalCut[vmax]:
                    vmax = i
                    vmaxval = verticalCut[vmax]          

        if hmaxval > vmaxval:
            visited[hash] = self.g(m, n, horizontalCut, verticalCut, horizontalStart, hmax, verticalStart, verticalEnd, visited) + self.g(m, n, horizontalCut, verticalCut, hmax + 1, horizontalEnd, verticalStart, verticalEnd, visited) + horizontalCut[hmax]
        else:
            visited[hash] = self.g(m, n, horizontalCut, verticalCut, horizontalStart, horizontalEnd, verticalStart, vmax, visited) + self.g(m, n, horizontalCut, verticalCut, horizontalStart, horizontalEnd, vmax + 1, verticalEnd, visited) + verticalCut[vmax]

        return visited[hash]

    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        return self.minimumCost2(m, n, horizontalCut, verticalCut, 0, m - 1, 0, n - 1, dict())
        # return self.g(m, n, horizontalCut, verticalCut, 0, m - 1, 0, n - 1, dict())



24300