C++ concise 0 ms solution, Pascal Rectangular, with explanation


  • 0
    P

    If change the robot begin corner to the top-right (m,n), and the finish corner to the down-left (0,0). The unique paths question is similar to Pascal triangle:

    1,  3,  6, 10, 15 <- robot start at (4,2)
    1,  2,  3,  4,  5
    1,  1,  1,  1,  1
    

    Create all the DP elements starts from(0,0). Number of unique paths equals to # from your left side + # from your down side. i.e. path( i, j ) = path( i-1, j ) +path( i, j-1 )

    Finally comes the code:

    class Solution {
    public:
      int uniquePaths(int m, int n) {
        int path[m][n];
        for ( int i = 0; i < m; i++ ) {
           for ( int j = 0; j < n; j++ ) {
              if ( i != 0 && j != 0 ) { path[i][j] = path[i-1][j] + path[i][j-1]; }
              else { path[i][j] = 1; }
           }
        }
        return path[m-1][n-1];
      }
    };

Log in to reply
 

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