The objective is to partition an m by n rectangular cake into 1x1 unit squares with the least total cost. Each horizontal cut between rows i and i+1 incurs a cost of horizontalCut[i]. Each vertical cut between columns j and j+1 incurs a cost of verticalCut[j]. The total cost is the sum of all cut costs.

Approach 1: Recursive Search with Memoization

A direct recursive method explores all possible cutting sequences. The state is defined by the coordinates of the top-left and bottom-right corners of a sub-rectangle. The function recursively tries every possible horizontal and vertical cut within the sub-rectangle, adding the cost of that cut to the minimum cost of cutting the resluting two smaller rectangles. Memoization prevents redundant calculations. This method is conceptually clear but has exponential time complexity, making it impractical for large inputs.

from functools import lru_cache
from typing import List

class RecursiveSolution:
    def min_cutting_cost(self, rows: int, cols: int, h_costs: List[int], v_costs: List[int]) -> int:
        @lru_cache(maxsize=None)
        def find_min(r_start, c_start, r_end, c_end):
            if r_start == r_end and c_start == c_end:
                return 0
            best = float('inf')
            # Try horizontal cuts
            for split_row in range(r_start, r_end):
                current_cost = h_costs[split_row]
                cost_above = find_min(r_start, c_start, split_row, c_end)
                cost_below = find_min(split_row + 1, c_start, r_end, c_end)
                best = min(best, current_cost + cost_above + cost_below)
            # Try vertical cuts
            for split_col in range(c_start, c_end):
                current_cost = v_costs[split_col]
                cost_left = find_min(r_start, c_start, r_end, split_col)
                cost_right = find_min(r_start, split_col + 1, r_end, c_end)
                best = min(best, current_cost + cost_left + cost_right)
            return best
        return find_min(0, 0, rows - 1, cols - 1)

Approach 2: Greedy Strategy

An efficient O(k log k) solution uses a greedy algorithm. Sort the horizontal and vertical cut costs in descending order. Maintain counters for the number of horizontal and vertical segments currently existing. Iteratively compare the highest remaining cost from each list. Choose the larger cost, multiply it by the current number of segments in the opposite direction (as this cut will be applied across all existing pieces in that dimension), add it to the total, and incremant the segment count for the chosen direction. Process all remaining costs.

from typing import List

def optimal_cutting_cost(rows: int, cols: int, h_costs: List[int], v_costs: List[int]) -> int:
    # Sort costs in descending order
    h_sorted = sorted(h_costs, reverse=True)
    v_sorted = sorted(v_costs, reverse=True)
    
    total = 0
    h_pieces = 1  # Number of horizontal segments
    v_pieces = 1  # Number of vertical segments
    
    i, j = 0, 0
    
    while i < len(h_sorted) and j < len(v_sorted):
        if h_sorted[i] >= v_sorted[j]:
            # Perform next most expensive horizontal cut
            total += h_sorted[i] * v_pieces
            h_pieces += 1
            i += 1
        else:
            # Perform next most expensive vertical cut
            total += v_sorted[j] * h_pieces
            v_pieces += 1
            j += 1
    # Process any remaining horizontal cuts
    while i < len(h_sorted):
        total += h_sorted[i] * v_pieces
        i += 1
    # Process any remaining vertical cuts
    while j < len(v_sorted):
        total += v_sorted[j] * h_pieces
        j += 1
    
    return total

# Example usage
print(optimal_cutting_cost(3, 2, [1, 3], [5]))  # Output: 13
print(optimal_cutting_cost(6, 3, [2, 3, 2, 3, 1], [1, 2]))  # Output: 41

The greedy algorithm works because each cut's contribution to the total cost is its cost multiplied by the number of pieces it will pass through at the time of cutting. Choosing the most expensive cuts first, when the multiplier is smallest, minimizes the total sum.