leetcode

commit b6ae8ad8a268b4df2fb91b57020c0132c84a468f
parent d39c61b0d9917f98e23684b32c00e4cea321ec40
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Mon, 29 May 2023 10:59:03 -0500

Completed unique paths ii using dart, dp, recursion, and memoization

Diffstat:
A
unique-paths-ii/unique-paths-ii.dart
 | 
33
+++++++++++++++++++++++++++++++++

1 file changed, 33 insertions(+), 0 deletions(-)
diff --git a/unique-paths-ii/unique-paths-ii.dart b/unique-paths-ii/unique-paths-ii.dart
@@ -0,0 +1,33 @@
+//Given a matrix return the total number of possible ways to traverse the grid from top left to
+//bottom right. The challenge in this one lies in the fact that there are certain 1's on the board
+//that are obstacles and thus can not be traversed. 
+//To solve this I took each right and down path for each tile to find out how many times each choice could
+//reach the end. To optimize this I saved that value to each memoized tile that way if a tile had been
+//traversed already the number of paths would not need to be recomputed.
+//Time: 298ms Beats: 100%
+//Memory: 145.7MB Beats: 100%
+
+class Solution {
+  int uniquePathsWithObstacles(List<List<int>> obstacleGrid) {
+      Map<String,int> memo = {};
+      return uniquePaths(obstacleGrid, [0,0], memo);
+  }
+  int uniquePaths(List<List<int>> grid , List<int> current_position, Map<String,int> memo){
+      if(current_position[0] >= grid.length || current_position[1] >= grid[0].length || grid[current_position[0]][current_position[1]] == 1){
+          return 0;
+      }
+      if(current_position[0] == grid.length - 1 && current_position[1] == grid[0].length - 1){
+          return 1;
+      }
+      String current = current_position[0].toString() + ' ' + current_position[1].toString();
+
+      if(memo.containsKey(current)){
+          return(memo[current] ?? 0);
+      }
+      int return_paths = 0;
+      return_paths += uniquePaths(grid, [current_position[0] + 1 , current_position[1]], memo);
+      return_paths += uniquePaths(grid, [current_position[0] , current_position[1] + 1], memo);
+      memo[current] = return_paths;
+      return return_paths;
+  }
+}