Number Of Ways Of Cutting A Pizza - Leetcode Solution

The problem "Number Of Ways Of Cutting A Pizza" on LeetCode asks us to find the number of ways to cut a pizza into pieces with at least one apple or tomato on each piece. The pizza is represented as a 2D array of size n x m, where the cell (i,j) contains either 'A' or 'T' or '.' representing an apple, tomato, or empty cell, respectively. A cut is defined as a straight line that divides the pizza into two pieces and goes through the center of any cell. We are also given the number of pieces we want to divide the pizza into.

One possible approach to solve this problem is to use dynamic programming. We can define a 3D dp array dp[i][j][k], where dp[i][j][k] represents the number of ways to cut the sub-pizza from cell (i,j) to the lower-right corner of the pizza into k pieces, such that each piece contains at least one apple or tomato.

We can observe that to compute dp[i][j][k], we need to consider all possible cuts that pass through cell (i,j) and divide the sub-pizza into two pieces. For each such cut, we can count the number of ways to cut the left piece into k-1 pieces and the right piece into 1 piece, such that each piece contains at least one apple or tomato. Then we can sum up all these counts to get the total number of ways to cut the sub-pizza from cell (i,j) into k pieces.

To speed up this computation, we can precompute two auxiliary arrays countA and countT, where countA[i][j] and countT[i][j] represent the number of apples and tomatoes, respectively, in the sub-pizza from cell (i,j) to the lower-right corner of the pizza. These arrays can be computed in O(nm) time using a simple dynamic programming approach.

Using these auxiliary arrays, we can check whether a cut passes through a cell containing an apple or tomato or not, and if not, we can skip that cut and move to the next one. This reduces the time complexity of our algorithm from O(np^3) to O(np^2), where p is the maximum number of cuts we need to consider.

The final answer is given by dp[0][0][k], which represents the number of ways to cut the entire pizza into k pieces, such that each piece contains at least one apple or tomato.

Here is the Python code for this approach:

class Solution:
    def ways(self, pizza: List[str], k: int) -> int:
        n, m = len(pizza), len(pizza[0])
        MOD = 10**9 + 7
        
        # Precompute auxiliary arrays countA and countT
        countA = [[0] * m for _ in range(n)]
        countT = [[0] * m for _ in range(n)]
        countA[-1][-1] = 1 if pizza[-1][-1] == 'A' else 0
        countT[-1][-1] = 1 if pizza[-1][-1] == 'T' else 0
        for i in range(n-2, -1, -1):
            countA[i][-1] = countA[i+1][-1] + (pizza[i][-1] == 'A')
            countT[i][-1] = countT[i+1][-1] + (pizza[i][-1] == 'T')
        for j in range(m-2, -1, -1):
            countA[-1][j] = countA[-1][j+1] + (pizza[-1][j] == 'A')
            countT[-1][j] = countT[-1][j+1] + (pizza[-1][j] == 'T')
        for i in range(n-2, -1, -1):
            for j in range(m-2, -1, -1):
                countA[i][j] = countA[i+1][j] + countA[i][j+1] - countA[i+1][j+1] + (pizza[i][j] == 'A')
                countT[i][j] = countT[i+1][j] + countT[i][j+1] - countT[i+1][j+1] + (pizza[i][j] == 'T')
        
        # Initialize the DP array dp
        dp = [[[0] * k for _ in range(m)] for _ in range(n)]
        dp[-1][-1][0] = 1 if pizza[-1][-1] != '.' else 0
        for i in range(n-2, -1, -1):
            dp[i][-1][0] = dp[i+1][-1][0] + (pizza[i][-1] != '.')
        for j in range(m-2, -1, -1):
            dp[-1][j][0] = dp[-1][j+1][0] + (pizza[-1][j] != '.')
            
        # Compute the DP array dp
        for i in range(n-2, -1, -1):
            for j in range(m-2, -1, -1):
                for t in range(1, k):
                    for x in range(i, n-1):
                        if countA[i][j] - countA[x+1][j] == 0:
                            dp[i][j][t] += dp[x+1][j][t-1]
                            dp[i][j][t] %= MOD
                    for y in range(j, m-1):
                        if countA[i][j] - countA[i][y+1] == 0:
                            dp[i][j][t] += dp[i][y+1][t-1]
                            dp[i][j][t] %= MOD
                    dp[i][j][t] %= MOD
        
        return dp[0][0][k-1]

The time complexity of this solution is O(nmp^2), where p is the maximum number of cuts we need to consider. The space complexity is also O(nmp).

1