Clear Java DP O(m*n*N) space O(m*n*N) time


  • 0
    L
    public class Solution {
        long[][][] dp;
        public int findPaths(int m, int n, int N, int i, int j) {
            if (N == 0) {
                return 0;
            }
            dp = new long[m][n][N];
            for (int o = 0; o < m; o++) {
                for (int p = 0; p < n; p++) {
                    for (int q = 0; q < N; q++) {
                    	dp[o][p][q] = -1l;
                    }
                }
            }
            return (int) helper(m, n, N, i, j);
        }
        
        long helper(int m, int n, int moves, int i, int j) {
            if (i < 0 || i == m || j < 0 || j == n) {
                // out
                return 1;
            }
            if (moves == 0) {
                // no moves
                return 0;
            }
            if (dp[i][j][moves-1] == -1) {
                // move to adjust and reduce moves
                dp[i][j][moves - 1] = (helper(m,n,moves-1,i-1,j) + helper(m,n,moves-1,i+1,j)
                    + helper(m,n,moves-1,i,j-1) + helper(m,n,moves-1,i,j+1)) % 1000000007;
            }
            return dp[i][j][moves-1];
        }
    }
    

Log in to reply
 

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