feat: solve No.403

BaffinLee · BaffinLee · commit ff24b1fc850b · 2023-08-27T22:26:37.000+08:00
diff --git a/401-500/403. Frog Jump.md b/401-500/403. Frog Jump.md
@@ -0,0 +1,80 @@
+# 403. Frog Jump
+
+- Difficulty: Hard.
+- Related Topics: Array, Dynamic Programming.
+- Similar Questions: Minimum Sideway Jumps, Solving Questions With Brainpower, Maximum Number of Jumps to Reach the Last Index.
+
+## Problem
+
+A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
+
+Given a list of `stones`' positions (in units) in sorted **ascending order**, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be `1` unit.
+
+If the frog's last jump was `k` units, its next jump must be either `k - 1`, `k`, or `k + 1` units. The frog can only jump in the forward direction.
+
+ 
+Example 1:
+
+```
+Input: stones = [0,1,3,5,6,8,12,17]
+Output: true
+Explanation: The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.
+```
+
+Example 2:
+
+```
+Input: stones = [0,1,2,3,4,8,9,11]
+Output: false
+Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.
+```
+
+ 
+**Constraints:**
+
+
+	
+- `2 <= stones.length <= 2000`
+	
+- `0 <= stones[i] <= 231 - 1`
+	
+- `stones[0] == 0`
+	
+- `stones` is sorted in a strictly increasing order.
+
+
+
+## Solution
+
+```javascript
+/**
+ * @param {number[]} stones
+ * @return {boolean}
+ */
+var canCross = function(stones) {
+    return stones[1] - stones[0] === 1
+        ? helper(stones, 1, 1, Array(stones.length).fill(0).map(() => ({})))
+        : false;
+};
+
+var helper = function(stones, i, k, dp) {
+    if (dp[i][k]) return false;
+    for (var j = i + 1; j < stones.length; j++) {
+        var diff = stones[j] - stones[i];
+        if (diff > k + 1) break;
+        if (diff < k - 1) continue;
+        if (helper(stones, j, diff, dp)) return true;
+    }
+    dp[i][k] = true;
+    return i === stones.length - 1;
+};
+```
+
+**Explain:**
+
+nope.
+
+**Complexity:**
+
+* Time complexity : O(n ^ 2).
+* Space complexity : O(n ^ 2).
