leetcode

commit 02dc98ae31f5f50ea6825710232ca2c153a2e0e6
parent d3b06283e4190fc81aaf469663ed46bfb9272901
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Sun, 28 May 2023 22:42:38 -0500

Completed jump game ii using dart, recursion, dp, and memoization

Diffstat:
A
jump-game-ii/jump-game-ii.dart
 | 
29
+++++++++++++++++++++++++++++

1 file changed, 29 insertions(+), 0 deletions(-)
diff --git a/jump-game-ii/jump-game-ii.dart b/jump-game-ii/jump-game-ii.dart
@@ -0,0 +1,29 @@
+//Given a list of nums where each number represents the total distance you can jump from that position
+//return the total number of jumps required to make it to the end.
+//Time: 1629ms Beats: 6.67%
+//Memory: 152.5MB Beats: 13.33%
+
+class Solution {
+  List<int> memo = [];
+  int jump(List<int> nums) {
+      memo = List.filled(nums.length, 1000000000);
+      return shortest_jump(nums, 0 , 0);
+  }
+  int shortest_jump(List<int> nums, int index, int jumps){
+      if(index >= nums.length - 1){
+          return jumps;
+      }
+      if(memo[index] <= jumps){
+          return 10000000;
+      }
+      memo[index] = jumps;
+      int min = 100000000;
+      for(int i = nums[index] ; i >= 1 ; --i){
+          int curr = shortest_jump(nums, index + i , jumps + 1);
+          if(curr < min){
+              min = curr;
+          }
+      }
+      return min;
+  }
+}