leetcode

commit 8fb057d53b1d104444a79dbcf58e0d4e1ce5d839
parent 56a916cbf81aa9c1e8dffda9ba95336491bb5c5a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 31 Mar 2023 12:48:29 +0200

Daily Problem

Diffstat:
A
Problems/1444.cpp
 | 
37
+++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 38 insertions(+), 0 deletions(-)
diff --git a/Problems/1444.cpp b/Problems/1444.cpp
@@ -0,0 +1,37 @@
+class Solution {
+  int n, m, mod = 1e9 + 7;
+  vector<vector<int>> count;
+  vector<vector<vector<int>>> dp = vector(10, vector(50, vector(50, -1)));
+
+  int rec(int row, int col, int left) {
+    if (count[row][col] == 0) return 0;
+    if (left == 0) return 1;
+    if (dp[left][row][col] != -1) return dp[left][row][col];
+
+    int &res = dp[left][row][col] = 0;
+    for (int i = row; i < n - 1; i++) {
+      if (count[row][col] - count[i + 1][col] <= 0) continue;
+      res = (res + rec(i + 1, col, left - 1)) % mod;
+    }
+
+    for (int i = col; i < m - 1; i++) {
+      if (count[row][col] - count[row][i + 1] <= 0) continue;
+      res = (res + rec(row, i + 1, left - 1)) % mod;
+    }
+
+    return res;
+  }
+
+public:
+  int ways(vector<string> &pizza, int k) {
+    n = pizza.size(), m = pizza[0].size();
+    count = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));
+
+    for (int i = n - 1; i >= 0; i--)
+      for (int j = m - 1; j >= 0; j--)
+        count[i][j] = count[i + 1][j] + count[i][j + 1] - count[i + 1][j + 1] +
+                      (pizza[i][j] == 'A');
+
+    return rec(0, 0, k - 1);
+  }
+};
diff --git a/README.md b/README.md
@@ -422,6 +422,7 @@ for solving problems.
 |  1436  |    Easy    | [Destination City](Problems/1436.cpp)                                                 |
 |  1438  |   Medium   | [Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit](Problems/1438.cpp)  |
 |  1443  |   Medium   | [Minimum Time to Collect All Apples in a Tree](Problems/1443.cpp)                                |
+|  1444  |    Hard    | [Number of Ways of Cutting a Pizza](Problems/1444.cpp)                                           |
 |  1462  |   Medium   | [Course Schedule IV](Problems/1462.cpp)                                                          |
 |  1466  |   Medium   | [Reorder Routes to Make All Paths Lead to the City Zero](Problems/1466.cpp)                      |
 |  1470  |    Easy    | [Shuffle the Array](Problems/1470.cpp)                                                           |