leetcode

commit 3c04fc7678a1a319974f793e4f33052ba87c720f
parent 65b51cdaee72b4f153aba29b03b437bfa573cbc4
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 18 Jun 2023 13:15:36 +0200

Daily Problem

Diffstat:
A
Problems/2328.cpp
 | 
34
++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 35 insertions(+), 0 deletions(-)
diff --git a/Problems/2328.cpp b/Problems/2328.cpp
@@ -0,0 +1,34 @@
+class Solution {
+  int MOD = 1E9 + 7;
+  int dp[1001][1001];
+
+  int n, m;
+  bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
+
+  int rec(const vector<vector<int>> &grid, int i, int j) {
+    if (dp[i][j] != -1) return dp[i][j];
+
+    static const int offs_x[4] = {0, 0, 1, -1};
+    static const int offs_y[4] = {1, -1, 0, 0};
+
+    int res = 0;
+    for (int k = 0; k < 4; k++) {
+      int x = i + offs_x[k], y = j + offs_y[k];
+      if (!valid(x, y)) continue;
+      if (grid[i][j] < grid[x][y]) res = (res + rec(grid, x, y) + 1) % MOD;
+    }
+    return dp[i][j] = res;
+  }
+
+public:
+  Solution() { memset(dp, 0xFF, sizeof(dp)); }
+  int countPaths(const vector<vector<int>> &grid) {
+    n = grid.size(), m = grid[0].size();
+
+    int res = m * n;
+    for (int i = 0; i < n; i++)
+      for (int j = 0; j < m; j++) res = (res + rec(grid, i, j)) % MOD;
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -546,6 +546,7 @@ for solving problems.
 |  2306  |    Hard    | [Naming a Company](Problems/2306.cpp)                                                            |
 |  2316  |   Medium   | [Count Unreachable Pairs of Nodes in an Undirected Graph](Problems/2316.cpp)                     |
 |  2326  |   Medium   | [Spiral Matrix IV](Problems/2326.cpp)                                                            |
+|  2328  |    Hard    | [Number of Increasing Paths in a Grid](Problems/2328.cpp)                                        |
 |  2331  |    Easy    | [Evaluate Boolean Binary Tree](Problems/2331.cpp)                                                |
 |  2336  |   Medium   | [Smallest Number in Infinite Set](Problems/2336.cpp)                                             |
 |  2343  |   Medium   | [Query Kth Smallest Trimmed Number](Problems/2343.cpp)                                           |