C++, dp, O(n^2) time, O(n) space


  • 5
    J

    The state transition equation is: memo[i][j] = memo[i][j-1] + memo[i-1][j]

    For example: A 3x4 grid, you need to reach bottom-right corner from top-left corner.

    We use memo[3][4] to save number of paths.

    x x x x
    x x x x 
    x x x x 
    

    Number of paths of first row is 1 1 1 1, because you can only go down and left, you only have one way to go to destination in row 0. So I init the row 0 with 1.

    And the second row, we only have one way to go to grid[1][0], is start->down->down.so memo[1][0] = 1.

    And for memo[1][1], you can go from grid[1][0] and grid[0][1], so memo[1][1] = memo[1][0]+memo[0][1], and the others are the similar.

    so the number of paths of 3x4 grid is:

    1 1 1  1 
    1 2 3  4 
    1 3 6 10, and return memo[2][3].
    

    And take a closer look at the question, you can just use O(n) space, because when you calculate m[i][j], you need to add up m[i][j-1] and m[i-1][j].

    In my solution, m[i][j-1] is m[i-1],has been calculated just before m[i]j, and m[i-1][j] is old m[i] saved in m[i].

    You add up old m[i] and new m[i-1], the answer saves in m[i].

    My English is not so good, I hope this can answer you question.

       int uniquePaths(int m, int n) {
            int *memo = new int[n];
            for(int i = 0; i < n; i++)
                memo[i] = 1;
            for(int i = 1 ; i < m; i++)
                for(int j = 1; j < n; j++)
                    memo[j] += memo[j-1];
            return memo[n-1];
        }

  • 0
    W

    Quite neat solution. Could you explain the logic behind this solution? Thanks in advance.


  • 0
    J
    This post is deleted!

  • 0
    J

    @whitehat Format is not so good, i hope it can help you.


  • 0

    @John1993: I have formatted your post, hope this helps.


  • 0
    J

    It always goes wrong when edit my answer, thank you so much!


  • 0
    W

    Thank you for the explanation


  • 0
    S

    Good idea to optimize the space complexity.


Log in to reply
 

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