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

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

• 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

• 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.

• @StefanPochmann Thanks man!

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