1555. Number of Ways of Cutting a Pizza
My accepted C++ solution to LeetCode problem 1555, Number of Ways of Cutting a Pizza, running in 7ms.
- Difficulty: Hard
- C++
- Runtime 7ms
- Memory 11.1MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
C++
Accepted on LeetCode — runtime 7ms, memory 11.1MB, accepted 2025-12-27.
class Solution {
public:
int ways(vector<string>& pizza, int k) {
int m = pizza.size(), n = pizza[0].size();
const int MOD = 1e9 + 7;
// Prefix sum of apples from (i,j) to bottom-right
vector<vector<int>> apples(m + 1, vector<int>(n + 1, 0));
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
apples[i][j] = (pizza[i][j] == 'A') + apples[i+1][j] + apples[i][j+1] - apples[i+1][j+1];
}
}
// dp[i][j][c] = ways to cut pizza from (i,j) into c pieces
vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(k + 1, 0)));
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
dp[i][j][1] = apples[i][j] > 0 ? 1 : 0;
for (int c = 2; c <= k; c++) {
// Horizontal cut
for (int ni = i + 1; ni < m; ni++) {
if (apples[i][j] - apples[ni][j] > 0) {
dp[i][j][c] = (dp[i][j][c] + dp[ni][j][c-1]) % MOD;
}
}
// Vertical cut
for (int nj = j + 1; nj < n; nj++) {
if (apples[i][j] - apples[i][nj] > 0) {
dp[i][j][c] = (dp[i][j][c] + dp[i][nj][c-1]) % MOD;
}
}
}
}
}
return dp[0][0][k];
}
};