Leetcode Problem 1444. Number of Ways of Cutting a Pizza

1444. Number of Ways of Cutting a Pizza

Leetcode Solutions

Initialize the cumulative sum matrix apples and the DP matrix dp with dimensions (k, rows, cols).
Populate the apples matrix with the number of apples in each sub-rectangle starting from the bottom-right corner.
Set the base case for the DP matrix: dp[0][row][col] is 1 if apples[row][col] is greater than 0, otherwise 0.
Iterate over the remaining cuts remain from 1 to k - 1.
For each state (remain, row, col), consider all possible horizontal and vertical cuts.
For each cut, check if the piece contains at least one apple using the apples matrix.
Update the DP state by adding the number of ways to cut the remaining piece.
Return dp[k-1][0][0] as the final answer.

Programming Language

Purpose:

General Question

Debug My Code

image/screenshot of info(optional)

Full Screen