DP O(n*m*N) time O(n*m) space, 13 ms


  • 1
    K
    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][n-1][1];
            }
            
            for(int j=0; j<n; ++j){
                ++dp[0][j][1];
                ++dp[m-1][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]][(k-1)%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;
        }
    };

  • 0
    J

    How does this work? To compute a cell you need all four adjacent values, so how is it OK to start at (0, 0)? Aren't (1, 0) and (0, 1) undetermined? And why the mod by 2 for k?


  • 1
    K

    @jakobcornell We do use all four adjacent values that's what the for-loop over t is for. We mod k 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.


  • 0
    S

    @jakobcornell

    This takes care of the 4 adjacent values

    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]][(k-1)%2]) % mod;
           }
    }             
    

  • 0
    J

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


Log in to reply
 

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