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);
}
}
}
Help! TLE, anyone could explain why and when using iterative dp is better than dfs and memorization?


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.
