Problem statement

https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/

Solution

Not very difficult from the point of view of idea, but it is easy to mix up with some border cases. The idea is to use dp with states dp(k, r, c), where k is number of cuts we still have, r and c` are the size of the rest part. Notice that the part we have always will have right bottom corner fixed. Then if we need to have:

  1. Precalculated cumulative sums to evaluate values in each part in O(1). Here Sum[r][c] is sum in number of apples in [0:r+1][0:c+1] part.
  2. When we cut we need to make sure than we have number of apples positive in both parts.
  3. If we have zero apples, we need to check k = 0 case more carefully.

Complexity

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

Code

class Solution:
    def ways(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]=='A')

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