Regarding the DFS method with memoization from the editorial solution.


  • 1
    M

    The following code came from the editorial solution. I am wondering how to deal with the cases with large m, n, N which can possibly result in overflow.

    Thanks.

    public class Solution {
        public int findPaths(int m, int n, int N, int i, int j) {
            int[][][] memo=new int[m][n][N+1];
            return findPaths(m,n,N,i,j,memo);
        }
        public int findPaths(int m, int n, int N, int i, int j,int[][][] memo) {
            if(i==m || j==n || i<0 ||j<0)
                return 1;
            if(N==0)
                return 0;
            if(memo[i][j][N]>0)
                return memo[i][j][N];
            memo[i][j][N]=findPaths(m,n,N-1,i-1,j,memo)+findPaths(m,n,N-1,i+1,j,memo)+findPaths(m,n,N-1,i,j-1,memo)+findPaths(m,n,N-1,i,j+1,memo);
            return memo[i][j][N];
        }
    }
    

  • 1
    M

    I have similar question.
    The DFS approach of the editorial solution cannot pass some cases of large input values. Simply changing int to long doesn't solve the issue.


  • 0
    M

    Long helps a little bit but does not solve the problem fundamentally. I was thinging converting to String and transform it back but it is very complicated.


  • 0
    T

    @MichaelPhelps said in Regarding the DFS method with memoization from the editorial solution.:

    public int findPaths(int m, int n, int N, int i, int j) {
    int[][][] memo=new int[m][n][N+1];
    return findPaths(m,n,N,i,j,memo);
    }
    public int findPaths(int m, int n, int N, int i, int j,int[][][] memo) {
    if(i==m || j==n || i<0 ||j<0)
    return 1;
    if(N==0)
    return 0;
    if(memo[i][j][N]>0)
    return memo[i][j][N];
    memo[i][j][N]=findPaths(m,n,N-1,i-1,j,memo)+findPaths(m,n,N-1,i+1,j,memo)+findPaths(m,n,N-1,i,j-1,memo)+findPaths(m,n,N-1,i,j+1,memo);
    return memo[i][j][N];
    }

    Add this constraint in c++ can pass and beats 84%
    if (i - N >= 0 && i + N < m && j - N >=0 && j + N < n)
    return 0;


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.