leetcode

commit 76a3e2f7cac294e52c95cc6bb8e604834716b7e9
parent 796ec663cba5857c88c1577eea5d8c364c811188
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun,  5 Feb 2023 15:47:54 +0100

Dynamic Programming I: Day 16

Diffstat:
A
Problems/0064.cpp
 | 
25
+++++++++++++++++++++++++
A
Problems/0221.cpp
 | 
18
++++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 45 insertions(+), 0 deletions(-)
diff --git a/Problems/0064.cpp b/Problems/0064.cpp
@@ -0,0 +1,25 @@
+class Solution {
+public:
+  int minPathSum(vector<vector<int>> &grid) {
+    int n = grid.size(), m = grid[0].size();
+    vector<vector<int>> mat(n, vector<int>(m, INT_MAX));
+    queue<pair<int, int>> q;
+
+    q.push({0, 0}), mat[0][0] = 0;
+    while (!q.empty()) {
+      auto [x, y] = q.front();
+      q.pop();
+      mat[x][y] += grid[x][y];
+      if (x + 1 < n) {
+        if (mat[x + 1][y] == INT_MAX) q.push({x + 1, y});
+        mat[x + 1][y] = min(mat[x + 1][y], mat[x][y]);
+      }
+      if (y + 1 < m) {
+        if (mat[x][y + 1] == INT_MAX) q.push({x, y + 1});
+        mat[x][y + 1] = min(mat[x][y + 1], mat[x][y]);
+      }
+    }
+
+    return mat.back().back();
+  }
+};
diff --git a/Problems/0221.cpp b/Problems/0221.cpp
@@ -0,0 +1,18 @@
+class Solution {
+public:
+  int maximalSquare(vector<vector<char>> &matrix) {
+    int n = matrix.size(), m = matrix[0].size(), res = 0;
+    vector<vector<int>> dp(n, vector<int>(m, 0));
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < m; j++) {
+        if (!i || !j || matrix[i][j] == '0') {
+          dp[i][j] = matrix[i][j] - '0';
+        } else {
+          dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
+        }
+        res = max(res, dp[i][j]);
+      }
+    }
+    return res * res;
+  }
+};
diff --git a/README.md b/README.md
@@ -60,6 +60,7 @@ for solving problems.
 |  0061  |   Medium   | [Rotate List](Problems/0061.cpp)                                                                 |
 |  0062  |   Medium   | [Unique Paths](Problems/0062.cpp)                                                                |
 |  0063  |   Medium   | [Unique Paths II](Problems/0063.cpp)                                                             |
+|  0064  |   Medium   | [Minimum Path Sum](Problems/0064.cpp)                                                            |
 |  0066  |    Easy    | [Plus One](Problems/0066.cpp)                                                                    |
 |  0067  |    Easy    | [Add Binary](Problems/0067.cpp)                                                                  |
 |  0070  |    Easy    | [Climbing Stairs](Problems/0070.cpp)                                                             |
@@ -142,6 +143,7 @@ for solving problems.
 |  0210  |   Medium   | [Course Schedule II](Problems/0210.cpp)                                                          |
 |  0213  |   Medium   | [House Robber II](Problems/0213.cpp)                                                             |
 |  0217  |    Easy    | [Contains Duplicate](Problems/0217.cpp)                                                          |
+|  0221  |   Medium   | [Maximal Square](Problems/0221.cpp)                                                              |
 |  0222  |   Medium   | [Count Complete Tree Nodes](Problems/0222.cpp)                                                   |
 |  0223  |   Medium   | [Rectangle Area](Problems/0223.cpp)                                                              |
 |  0226  |    Easy    | [Invert Binary Tree](Problems/0226.cpp)                                                          |