leetcode

commit 39455d512cb5a106281ff50b767e200a9fa02937
parent ed4fd2b6d328e91aa05e7c4eda3d386a846b68da
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 25 Jun 2023 11:35:46 +0200

Daily Problem

Diffstat:
A
Problems/1575.cpp
 | 
21
+++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 22 insertions(+), 0 deletions(-)
diff --git a/Problems/1575.cpp b/Problems/1575.cpp
@@ -0,0 +1,21 @@
+class Solution {
+  static const int MOD = 1E9 + 7;
+  int dp[101][201];
+
+public:
+  Solution() { memset(dp, 0xFF, sizeof(dp)); }
+
+  int countRoutes(const vector<int> &loc, int start, int finish, int fuel) {
+    if (fuel < 0) return 0;
+    if (dp[start][fuel] >= 0) return dp[start][fuel];
+
+    int res = (start == finish);
+    for (int i = 0; i < loc.size(); i++) {
+      if (i == start) continue;
+      int solution =
+          countRoutes(loc, i, finish, fuel - abs(loc[start] - loc[i]));
+      res = (res + solution) % MOD;
+    }
+    return dp[start][fuel] = res;
+  }
+};
diff --git a/README.md b/README.md
@@ -487,6 +487,7 @@ for solving problems.
 |  1567  |   Medium   | [Maximum Length of Subarray With Positive Product](Problems/1567.cpp)                            |
 |  1569  |    Hard    | [Number of Ways to Reorder Array to Get Same BST](Problems/1569.cpp)                             |
 |  1572  |    Easy    | [Matrix Diagonal Sum](Problems/1572.cpp)                                                         |
+|  1575  |   Medium   | [Count All Possible Routes](Problems/1575.cpp)                                                   |
 |  1579  |    Hard    | [Remove Max Number of Edges to Keep Graph Fully Traversable](Problems/1579.cpp)                  |
 |  1584  |   Medium   | [Min Cost to Connect All Points](Problems/1584.cpp)                                              |
 |  1603  |    Easy    | [Design Parking System](Problems/1603.cpp)                                                       |