Update Out of Boundary Paths.java

varunu28 · web-flow · commit 740bcab2ec19 · 2024-01-26T07:06:02.000-08:00
diff --git a/Medium/Out of Boundary Paths.java b/Medium/Out of Boundary Paths.java
@@ -1,34 +1,26 @@
 class Solution {
-  private final int MODULUS = 1000000000 + 7;
-  
-  public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
-    int dp[][] = new int[m][n];
-    dp[startRow][startColumn] = 1;
-    int count = 0;
-    for (int currMove = 1; currMove <= maxMove; currMove++) {
-      int[][] temp = new int[m][n];
-      for (int i = 0; i < m; i++) {
-        for (int j = 0; j < n; j++) {
-          if (i == m - 1) {
-            count = (count + dp[i][j]) % MODULUS;
-          }
-          if (j == n - 1) {
-            count = (count + dp[i][j]) % MODULUS;
-          }
-          if (i == 0) {
-            count = (count + dp[i][j]) % MODULUS;
-          }
-          if (j == 0) {
-            count = (count + dp[i][j]) % MODULUS;
-          }
-          temp[i][j] = (
-              ((i > 0 ? dp[i - 1][j] : 0) + (i < m - 1 ? dp[i + 1][j] : 0)) % MODULUS +
-              ((j > 0 ? dp[i][j - 1] : 0) + (j < n - 1 ? dp[i][j + 1] : 0)) % MODULUS
-          ) % MODULUS;
+
+    private static final int MOD = 1000_000_007;
+
+    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
+        Integer[][][] dp = new Integer[m][n][maxMove + 1];
+        return findPaths(m, n, maxMove, startRow, startColumn, dp);
+    }
+
+    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn, Integer[][][] dp) {
+        if (startRow == m || startColumn == n || startRow < 0 || startColumn < 0) {
+            return 1;
+        }
+        if (maxMove == 0) {
+            return 0;
+        }
+        if (dp[startRow][startColumn][maxMove] != null) {
+            return dp[startRow][startColumn][maxMove];
         }
-      }
-      dp = temp;
+        return dp[startRow][startColumn][maxMove] = (
+            (findPaths(m, n, maxMove - 1, startRow - 1, startColumn, dp) +
+            findPaths(m, n, maxMove - 1, startRow + 1, startColumn, dp)) % MOD +
+            (findPaths(m, n, maxMove - 1, startRow, startColumn - 1, dp) +
+            findPaths(m, n, maxMove - 1, startRow, startColumn + 1, dp)) % MOD) % MOD; 
     }
-    return count;
-  }
 }
