# Share my java dp memoization solution

• 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;
}
}``````

• 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);
}
}``````

• 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];
``````

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