# 34 ms JAVA solution, dp, with restrictions on maximum steps for each cell

• Pretty straightforward

``````    public int findPaths(int m, int n, int N, int i, int j) {
if (N==0) return 0;
int[][][] dp = new int[m][n][N];
dp[i][j][0] = 1;
int[][] maxstep = new int[m][n];
for (int i1=0;i1<m;i1++)
for (int j1=0;j1<n;j1++)
maxstep[i1][j1] = N-(Math.min(Math.min(Math.min(i1+1,j1+1),m-i1),n-j1));
for (int k=0;k<N;k++){
for (int i1=0;i1<m;i1++){
for(int j1=0;j1<n;j1++){
if (i1>0 && maxstep[i1-1][j1]>k){
dp[i1-1][j1][k+1] += dp[i1][j1][k];
dp[i1-1][j1][k+1]%=(1000000000 + 7);
}
if (j1>0 && maxstep[i1][j1-1]>k){
dp[i1][j1-1][k+1] += dp[i1][j1][k];
dp[i1][j1-1][k+1]%=(1000000000 + 7);
}
if (i1<m-1 && maxstep[i1+1][j1]>k){
dp[i1+1][j1][k+1] += dp[i1][j1][k];
dp[i1+1][j1][k+1]%=(1000000000 + 7);
}
if (j1<n-1 && maxstep[i1][j1+1]>k){
dp[i1][j1+1][k+1] += dp[i1][j1][k];
dp[i1][j1+1][k+1]%=(1000000000 + 7);
}
}
}
}
int res = 0;
for (int i1=0;i1<m;i1++){
for (int k=0;k<N;k++){
res+=(long)(dp[i1][0][k]+dp[i1][n-1][k])%(1000000000 + 7);
res%=(1000000000 + 7);
}
}
for (int j1=0;j1<n;j1++){
for (int k=0;k<N;k++){
res+=(long)(dp[0][j1][k]+dp[m-1][j1][k])%(1000000000 + 7);
res%=(1000000000 + 7);
}
}
return res%(1000000000 + 7);
}
``````

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