Add solution #1444

JoshCrozier · JoshCrozier · commit ad917fd938d6 · 2025-04-14T11:12:58.000-05:00
diff --git a/README.md b/README.md
@@ -1,4 +1,4 @@
-# 1,306 LeetCode solutions in JavaScript
+# 1,307 LeetCode solutions in JavaScript
 
 [https://leetcodejavascript.com](https://leetcodejavascript.com)
 
@@ -1102,6 +1102,7 @@
 1441|[Build an Array With Stack Operations](./solutions/1441-build-an-array-with-stack-operations.js)|Medium|
 1442|[Count Triplets That Can Form Two Arrays of Equal XOR](./solutions/1442-count-triplets-that-can-form-two-arrays-of-equal-xor.js)|Medium|
 1443|[Minimum Time to Collect All Apples in a Tree](./solutions/1443-minimum-time-to-collect-all-apples-in-a-tree.js)|Medium|
+1444|[Number of Ways of Cutting a Pizza](./solutions/1444-number-of-ways-of-cutting-a-pizza.js)|Hard|
 1446|[Consecutive Characters](./solutions/1446-consecutive-characters.js)|Easy|
 1447|[Simplified Fractions](./solutions/1447-simplified-fractions.js)|Medium|
 1448|[Count Good Nodes in Binary Tree](./solutions/1448-count-good-nodes-in-binary-tree.js)|Medium|
diff --git a/solutions/1444-number-of-ways-of-cutting-a-pizza.js b/solutions/1444-number-of-ways-of-cutting-a-pizza.js
@@ -0,0 +1,64 @@
+/**
+ * 1444. Number of Ways of Cutting a Pizza
+ * https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/
+ * Difficulty: Hard
+ *
+ * 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.
+ */
+
+/**
+ * @param {string[]} pizza
+ * @param {number} k
+ * @return {number}
+ */
+var ways = function(pizza, k) {
+  const MOD = 1e9 + 7;
+  const rows = pizza.length;
+  const cols = pizza[0].length;
+  const appleCount = new Array(rows + 1).fill().map(() => new Array(cols + 1).fill(0));
+  const dpCache = new Array(rows + 1).fill().map(() =>
+    new Array(cols + 1).fill().map(() => new Array(k + 1).fill(-1))
+  );
+
+  for (let i = rows - 1; i >= 0; i--) {
+    for (let j = cols - 1; j >= 0; j--) {
+      appleCount[i][j] = (pizza[i][j] === 'A' ? 1 : 0)
+        + appleCount[i + 1][j] + appleCount[i][j + 1] - appleCount[i + 1][j + 1];
+    }
+  }
+
+  return countWays(0, 0, k - 1);
+
+  function countWays(row, col, cutsLeft) {
+    if (appleCount[row][col] === 0) return 0;
+    if (cutsLeft === 0) return 1;
+    if (dpCache[row][col][cutsLeft] !== -1) return dpCache[row][col][cutsLeft];
+
+    let result = 0;
+
+    for (let i = row + 1; i < rows; i++) {
+      if (appleCount[row][col] - appleCount[i][col] > 0) {
+        result = (result + countWays(i, col, cutsLeft - 1)) % MOD;
+      }
+    }
+
+    for (let j = col + 1; j < cols; j++) {
+      if (appleCount[row][col] - appleCount[row][j] > 0) {
+        result = (result + countWays(row, j, cutsLeft - 1)) % MOD;
+      }
+    }
+
+    dpCache[row][col][cutsLeft] = result;
+    return result;
+  }
+};
