62. Unique Paths

Hint

class Solution {
public:
    int uniquePaths(int m, int n)
    {
        // Create a 2D vector 'dp' with m rows and n columns, initialized to 1.
        // dp[i][j] represents the number of unique paths to reach cell (i, j).
        
        // Iterate through the grid starting from cell (1,1) since the first row
        // and first column can only be reached in one way (all 1's).
        for ()
        {
            for ()
            {
                // The number of ways to reach cell (i, j) is the sum of the ways
                // to reach the cell directly above it (i-1, j) and the cell
                // directly to the left of it (i, j-1).
            }
        }
        
        // The bottom-right corner of the grid will contain the total number
        // of unique paths from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1).
    }
};

Solution

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

• T:
  $O(M\cdot N)$
• S:
  $O(M\cdot N)$