leetcode

commit 23b471439c768422719febcd8b75a4c8f9e995ce
parent 422ba403df8ba4705f5f18e3f910fb4035c2409c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 27 Aug 2023 22:09:28 +0200

Daily Problem

Diffstat:
A
Problems/0403.cpp
 | 
25
+++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 26 insertions(+), 0 deletions(-)
diff --git a/Problems/0403.cpp b/Problems/0403.cpp
@@ -0,0 +1,25 @@
+class Solution {
+    bool dp[2001][2001] = {false};
+    unordered_map<int, int> um;
+
+    bool rec(const vector<int> &stones, int idx = 0, int k = 0) {
+        if (idx == stones.size() - 1) return true;
+        if (dp[k][idx]) return false;
+        dp[k][idx] = true;
+
+        for (int jmp = k + 1; jmp >= k - 1 && jmp > 0; jmp--) {
+            if (um.count(stones[idx] + jmp)) {
+                if (rec(stones, um[stones[idx] + jmp], jmp)) return true;
+            }
+        }
+
+        return false;
+    }
+
+  public:
+    bool canCross(const vector<int> &stones) {
+        for (int i = 0; i < stones.size(); i++)
+            um.insert({stones[i], i});
+        return rec(stones);
+    }
+};
diff --git a/README.md b/README.md
@@ -266,6 +266,7 @@ for solving problems.
 |  0394  |   Medium   | [Decode String](Problems/0394.cpp)                                                               |
 |  0399  |   Medium   | [Evaluate Division](Problems/0399.cpp)                                                           |
 |  0402  |   Medium   | [Remove K Digits](Problems/0402.cpp)                                                             |
+|  0403  |    Hard    | [Frog Jump](Problems/0403.cpp)                                                                   |
 |  0404  |    Easy    | [Sum of Left Leaves](Problems/0404.cpp)                                                          |
 |  0406  |   Medium   | [Queue Reconstruction by Height](Problems/0406.cpp)                                              |
 |  0409  |    Easy    | [Longest Palindrome](Problems/0409.cpp)                                                          |