Help! TLE, anyone could explain why and when using iterative dp is better than dfs and memorization?


  • 0
    N
    int M, N;
    int res = 0;
    int[] directions = {0, 1, 0, -1, 0};
    static final int mod = 1000000007;
    public int findPaths(int m, int n, int k, int i, int j) {
        M = m;
        N = n;
        // dp[i][j][k] means the number of ways to get to i, j when there are k steps left
        // note that dp[i][j][k] only depends on dp[i][j][k - 1], so compress to two dimension array;
        dfs(i, j, k, new int[M][N]);
        return res % mod;
    }
    private void dfs(int i, int j, int k, int[][] dp) {
        if (k == 0) {
            return;
        }
        for (int m = 0; m < 4; m++) {
            int x = directions[m] + i;
            int y = directions[m + 1] + j;
            if ((x == -1 || x == M || y == -1 || y == N)) {
                res++;
            } else {
                dp[x][y] += dp[i][j];
                dfs(x, y, k - 1, dp);
            }
        }
    }

  • 0
    N

    Hey guys, when encountering DP problems, I am always wondering if we should just fill out the array iteratively or using the dfs and memorazation approach like this one? Thanks


  • 2

    Not sure what you mean with "memorization" and "memorazation", but you're not using memoization (if you misspell it two out of two times, I'll have to point it out :-). Because you're recomputing stuff over and over again. The whole point of memoization is to not do that. You should check whether you have computed a value already and only compute it if you haven't yet.


  • 0
    N

    @StefanPochmann Thanks man!


Log in to reply
 

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