0ms, 5-lines DP Solution in C++ with Explanations


  • 210

    This is a fundamental DP problem. First of all, let's make some observations.

    Since the robot can only move right and down, when it arrives at a point, there are only two possibilities:

    1. It arrives at that point from above (moving down to that point);
    2. It arrives at that point from left (moving right to that point).

    Thus, we have the following state equations: suppose the number of paths to arrive at a point (i, j) is denoted as P[i][j], it is easily concluded that P[i][j] = P[i - 1][j] + P[i][j - 1].

    The boundary conditions of the above equation occur at the leftmost column (P[i][j - 1] does not exist) and the uppermost row (P[i - 1][j] does not exist). These conditions can be handled by initialization (pre-processing) --- initialize P[0][j] = 1, P[i][0] = 1 for all valid i, j. Note the initial value is 1 instead of 0!

    Now we can write down the following (unoptimized) code.

    class Solution {
        int uniquePaths(int m, int n) {
            vector<vector<int> > path(m, vector<int> (n, 1));
            for (int i = 1; i < m; i++)
                for (int j = 1; j < n; j++)
                    path[i][j] = path[i - 1][j] + path[i][j - 1];
            return path[m - 1][n - 1];
        }
    };
    

    As can be seen, the above solution runs in O(n^2) time and costs O(m*n) space. However, you may have observed that each time when we update path[i][j], we only need path[i - 1][j] (at the same column) and path[i][j - 1] (at the left column). So it is enough to maintain two columns (the current column and the left column) instead of maintaining the full m*n matrix. Now the code can be optimized to have O(min(m, n)) space complexity.

    class Solution {
        int uniquePaths(int m, int n) {
            if (m > n) return uniquePaths(n, m); 
            vector<int> pre(m, 1);
            vector<int> cur(m, 1);
            for (int j = 1; j < n; j++) {
                for (int i = 1; i < m; i++)
                    cur[i] = cur[i - 1] + pre[i];
                swap(pre, cur);
            }
            return pre[m - 1];
        }
    };
    

    Further inspecting the above code, we find that keeping two columns is used to recover pre[i], which is just cur[i] before its update. So there is even no need to use two vectors and one is just enough. Now the space is further saved and the code also gets much shorter.

    class Solution {
        int uniquePaths(int m, int n) {
            if (m > n) return uniquePaths(n, m);
            vector<int> cur(m, 1);
            for (int j = 1; j < n; j++)
                for (int i = 1; i < m; i++)
                    cur[i] += cur[i - 1]; 
            return cur[m - 1];
        }
    }; 
    

    Well, till now, I guess you may even want to optimize it to O(1) space complexity since the above code seems to rely on only cur[i] and cur[i - 1]. You may think that 2 variables is enough? Well, it is not. Since the whole cur needs to be updated for n - 1 times, it means that all of its values need to be saved for next update and so two variables is not enough.


  • 2
    W

    For the second solution. I think it should return pre[m-1] not cur[m-1]


  • 0

    Hi, you are right. Thanks for remind. I have updated my code.


  • 0
    J

    clear explanation!


  • 0

    Hi, jayasuryajeyakodi. You are very welcome.


  • 0
    V

    oh,shit! it is great. better than the handbook.


  • 0
    A

    swap is awesome


  • 0
    J

    greatest explaination ever seen


  • 1
    P

    I think there is no need swapping m and n even if m > n.


  • 0

    Hi, @paperplane1230. I swap m and n only to make the running time O(min(m, n)) :-)


  • 0
    A

    Are you initializing the matrix with 1 ie:[111
    111
    111]


  • 0
    H

    Such a genius


  • 0
    D

    Awesome solution!I Learn much from you,thanks. The way you thinking must be very clear,and the patient .


  • 0
    L

    this is great Thanks!!!


  • 0
    R

    hi, its amazing explanation thank you so much


  • 0
    A

    Nice explanation


  • 7
    L

    @jianchao-li-fighter, one minor correction. The solution runs in O(m*n) time and not O(n^2) as you noted in solution description. Btw, thanks for awesome explanation.


  • 0
    This post is deleted!

  • 0
    I

    @jianchao.li.fighter Can you provide the solution for all four directions please?


  • 0
    M

    very beautiful !


Log in to reply
 

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