Number of ways of cutting a pizza

Array Dynamic Programming Memoization Matrix Prefix Sum

61.6% acceptance

Feb 25, 2026

1906

Given a rectangular pizza represented as a rows x cols matrix containing the following characters: 'A' (an apple) and '.' (empty cell) and given the integer k. You have to cut the pizza into k pieces using k-1 cuts. For each cut you choose the direction: vertical or horizontal, then you choose a cut position at the cell boundary and cut the pizza into two pieces. If you cut the pizza vertically, give the left part of the pizza to a person. If you cut the pizza horizontally, give the upper part of the pizza to a person. Give the last piece of pizza to the last person. Return the number of ways of cutting the pizza such that each piece contains at least one apple. Since the answer can be a huge number, return this modulo 10^9 + 7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn ways(pizza: Vec<String>, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let rows = pizza.len();
    let cols = pizza[0].len();
    let k = k as usize;
    let mut suffix = vec![vec![0i32; cols + 1]; rows + 1];
    for r in (0..rows).rev() {
      for c in (0..cols).rev() {
        suffix[r][c] = (if pizza[r].as_bytes()[c] == b'A' { 1 } else { 0 })
          + suffix[r+1][c] + suffix[r][c+1] - suffix[r+1][c+1];
      }
    }
    let mut dp = vec![vec![vec![0i64; cols]; rows]; k];
    for r in 0..rows {
      for c in 0..cols {
        if suffix[r][c] > 0 { dp[0][r][c] = 1; }
      }
    }
    for ki in 1..k {
      for r in 0..rows {
        for c in 0..cols {
          if suffix[r][c] == 0 { continue; }
          for r2 in r+1..rows {
            if suffix[r][c] - suffix[r2][c] > 0 {
              dp[ki][r][c] = (dp[ki][r][c] + dp[ki-1][r2][c]) % MOD;
            }
          }
          for c2 in c+1..cols {
            if suffix[r][c] - suffix[r][c2] > 0 {
              dp[ki][r][c] = (dp[ki][r][c] + dp[ki-1][r][c2]) % MOD;
            }
          }
        }
      }
    }
    dp[k-1][0][0] as i32
  }
}