Share my java dp memoization solution


  • 0
    J

    The following memoization solution takes 40ms, slower than the other bottom-up solutions posted.

    public class Solution {
        private static long max = 1000000007;
        public int findPaths(int m, int n, int N, int i, int j) {
            return (int) findPaths(m, n, N, i, j, new HashMap<Integer, Long>());
        }
        
        public long findPaths(int m, int n, int N, int i, int j, Map<Integer, Long> cache) {
            if (i==-1 || j==-1 || i==m || j==n) {
                // out of boundary
                return 1;
            }
            
            int key = i * 10000 + j * 100 + N;
            Long p = cache.get(key);
            if (p != null) {
                return p;
            }
            
            if (N == 0) {
                // still within boundary, but exceeds max moves allowed
                return 0;
            }
            
            long paths = 
                (findPaths(m, n, N-1, i-1, j, cache) +
                findPaths(m, n, N-1, i+1, j, cache) +
                findPaths(m, n, N-1, i, j-1, cache) +
                findPaths(m, n, N-1, i, j+1, cache)) % max;
            cache.put(key, paths);
            return paths;
        }
    }

  • 0

    Just curious why your solution can pass the test, but my below one will TLE

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

  • 0
    J

    Your memo is initialized to be all 0, but you shouldn't use 0 as a way to check if the cache is available, as 0 could well just be the actual cached result. Initialize your memo with all -1 and check cache using

    if(memo[i][j][N]>-1)
         return memo[i][j][N]; 
    

Log in to reply
 

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