leetcode

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

minimum-path-sum.dart (1311B)

      1 //Find the path from the top left to bottom right that
      2 //has to lowest possible sum. To do this I used DP with
      3 //recursion and memoization to remember the lowest possible
      4 //values for each spot on the board.
      5 //Time: 255ms Beats: 93.75%
      6 //Memory: 143.7MB Beats: 75%
      7 
      8 class Solution {
      9   int minPathSum(List<List<int>> grid) {
     10       return recurse(grid , [0,0], {});
     11   }
     12 
     13 
     14   int recurse(List<List<int>> grid , List<int> position, Map<String,int> memo){
     15       int xpos = position[0];
     16       int ypos = position[1];
     17       String current_str = xpos.toString() + " " + ypos.toString();
     18       if(memo.containsKey(current_str)){
     19         int return_val = memo[current_str] ?? 0;
     20         return return_val;
     21       }
     22 
     23       if(xpos == grid.length - 1 && ypos == grid[0].length - 1){
     24           return grid[xpos][ypos];
     25       }
     26       int down = 1000000;
     27       int right = 1000000;
     28       if(xpos < grid.length - 1){
     29         right = recurse(grid, [xpos + 1 , ypos], memo);
     30       }
     31       if(ypos < grid[0].length - 1){
     32         down = recurse(grid, [xpos , ypos + 1], memo);
     33       }
     34       int return_int = 0;
     35       if(down < right){
     36           return_int =  down + grid[xpos][ypos];
     37       }
     38       else{
     39           return_int = right + grid[xpos][ypos];
     40       } 
     41       memo[current_str] = return_int;
     42       return(return_int);
     43 
     44   }
     45 }