class Solution {
int dx[4] = {0, 0, 1, 1};
int dy[4] = {1, 1, 0 ,0};
public:
long findPaths(int m, int n, int N, int i, int j) {
int mod = (10E8) + 7;
vector<vector<vector<long>>> dp(m, vector<vector<long>>(n, vector<long>(2)));
for(int i=0; i<m; ++i){
++dp[i][0][1];
++dp[i][n1][1];
}
for(int j=0; j<n; ++j){
++dp[0][j][1];
++dp[m1][j][1];
}
for(int k=2; k<=N; ++k){
for(int i=0; i<m; ++i){
for(int j=0; j<n; ++j){
dp[i][j][k%2] = 0;
for(int t=0; t<4; ++t){
if(outOfBounds(m,n, i+dx[t], j+dy[t])){
dp[i][j][k%2] = (dp[i][j][k%2]+1L) % mod;
} else {
dp[i][j][k%2] = (dp[i][j][k%2] + dp[i+dx[t]][j+dy[t]][(k1)%2]) % mod;
}
}
}
}
}
return dp[i][j][N%2] % mod;
}
bool outOfBounds(int m, int n, int i, int j){
return i < 0  j < 0  i >= m  j >= n;
}
};
DP O(n*m*N) time O(n*m) space, 13 ms


@jakobcornell We do use all four adjacent values that's what the forloop over
t
is for. We modk
by 2 to reduce the amount of extra memory needed, since we don't need to keep all of the data values from every previous iteration, only the data values from the previous iteration is needed.

@kevin36 OK, this makes sense now. I didn't realize before that you do a pass through the grid for each move. Nice solution!