leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

jump-game-ii.dart (852B)

      1 //Given a list of nums where each number represents the total distance you can jump from that position
      2 //return the total number of jumps required to make it to the end.
      3 //Time: 1629ms Beats: 6.67%
      4 //Memory: 152.5MB Beats: 13.33%
      5 
      6 class Solution {
      7   List<int> memo = [];
      8   int jump(List<int> nums) {
      9       memo = List.filled(nums.length, 1000000000);
     10       return shortest_jump(nums, 0 , 0);
     11   }
     12   int shortest_jump(List<int> nums, int index, int jumps){
     13       if(index >= nums.length - 1){
     14           return jumps;
     15       }
     16       if(memo[index] <= jumps){
     17           return 10000000;
     18       }
     19       memo[index] = jumps;
     20       int min = 100000000;
     21       for(int i = nums[index] ; i >= 1 ; --i){
     22           int curr = shortest_jump(nums, index + i , jumps + 1);
     23           if(curr < min){
     24               min = curr;
     25           }
     26       }
     27       return min;
     28   }
     29 }