Problem statement

https://binarysearch.com/problems/Cut-Matrix/

Solution

Equal to 1444. Number of Ways of Cutting a Pizza.

Complexity

It is O(kmn(m+n)) for time and O(kmn) for space.

Code

class Solution:
    def solve(self, pizza, K):
        m, n, MOD = len(pizza), len(pizza[0]), 10**9 + 7
        Sum = [[0] * (n + 1) for _ in range(m + 1)]
        for r in range(m - 1, -1, -1):
            for c in range(n - 1, -1, -1):
                Sum[r][c] = Sum[r][c+1] + Sum[r+1][c] - Sum[r+1][c+1] + (pizza[r][c]== 1)

        @lru_cache(None)
        def dp(k, r, c):
            if k == 0: return int(Sum[r][c] > 0)
            ans = 0
            
            for nr in range(r + 1, m):  # cut horizontally
                if Sum[r][c] > Sum[nr][c] > 0:
                    ans += dp(k - 1, nr, c)
                            
            for nc in range(c + 1, n):  # cut vertically
                if Sum[r][c] > Sum[r][nc] > 0:
                    ans += dp(k - 1, r, nc)
            return ans % MOD

        return dp(K - 1, 0, 0)