1444.js

/** ------------------------------------------------------------------------------
 * 
 * 2023-03-31
 * Number of Ways of Cutting a Pizza
 * https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/
 * 
 ------------------------------------------------------------------------------ */

/**
 * @param {string[]} pizza
 * @param {number} k
 * @return {number}
 */
const MOD = 1000000007;

var ways = function (pizza, k) {
  const rows = pizza.length;
  const cols = pizza[0].length;
  const dp = Array.from({ length: k }, () =>
    Array.from({ length: rows }, () => Array.from({ length: cols }, () => -1)),
  );

  return cut(0, 0, k - 1);

  function cut(r, c, cutsLeft) {
    if (dp[cutsLeft][r][c] !== -1) {
      return dp[cutsLeft][r][c];
    }

    let count = 0;

    if (cutsLeft === 0) {
      for (let i = r; i < rows; i++) {
        for (let j = c; j < cols; j++) {
          if (pizza[i][j] === "A") {
            count++;
          }
        }
      }

      return count > 0 ? 1 : 0;
    }

    for (let i = r + 1; i < rows; i++) {
      if (countApples(r, c, i - 1, cols - 1) > 0) {
        count = (count + cut(i, c, cutsLeft - 1)) % MOD;
      }
    }

    for (let j = c + 1; j < cols; j++) {
      if (countApples(r, c, rows - 1, j - 1) > 0) {
        count = (count + cut(r, j, cutsLeft - 1)) % MOD;
      }
    }

    dp[cutsLeft][r][c] = count;
    return count;
  }

  function countApples(r1, c1, r2, c2) {
    let count = 0;

    for (let r = r1; r <= r2; r++) {
      for (let c = c1; c <= c2; c++) {
        count += pizza[r][c] === "A" ? 1 : 0;
      }
    }

    return count;
  }
};

console.log(ways(["A..", "AAA", "..."], 3));