Java Solution, DP with space compression

• `DP[i][j][k]` stands for how many possible ways to walk into cell `j,k` in step `i`, `DP[i][j][k]` only depends on `DP[i - 1][j][k]`, so we can compress 3 dimensional dp array to 2 dimensional.

``````public class Solution {
public int findPaths(int m, int n, int N, int i, int j) {
if (N <= 0) return 0;

final int MOD = 1000000007;
int[][] count = new int[m][n];
count[i][j] = 1;
int result = 0;

int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

for (int step = 0; step < N; step++) {
int[][] temp = new int[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
for (int[] d : dirs) {
int nr = r + d[0];
int nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
result = (result + count[r][c]) % MOD;
}
else {
temp[nr][nc] = (temp[nr][nc] + count[r][c]) % MOD;
}
}
}
}
count = temp;
}

return result;
}
}
``````

• This post is deleted!

• Great Solution! I emulate your method!

``````public class Solution {
public int findPaths(int m, int n, int N, int i, int j) {
int res=0;
if(N<=0) return 0;

int[][] dp=new int[m][n];
int[][] dirs=new int[][]{{-1,0},{1,0},{0,1},{0,-1}};

for(int[] ele:dirs){
int x=ele[0]+i;
int y=ele[1]+j;
if(x<0||x>=m||y<0||y>=n){
res++;
}else{
dp[x][y]=1;
}
}

if(N==1){
return res;
}

int max=1000000007;
for(int p=2;p<=N;p++){
int[][] temp=new int[m][n];
for(int k=0;k<m;k++){
for(int q=0;q<n;q++){
for(int[] dir:dirs){
int x = dir[0]+k;
int y = dir[1]+q;

if(x<0||x>=m||y<0||y>=n){
res=(res+dp[k][q])%max;
}else{
temp[x][y]=(temp[x][y]+dp[k][q])%max;
}
}
}
}

dp=temp;
}

return res;
}
}
``````

• I like this method best. Each N is the sum of N-1 from four directions

• Brilliant and concise!
temp[][] stores the k-th move while count[][] stores the k-1 th.

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