🌱 Keegan's Digital Garden

62. Unique Paths

2 min read

📝 Problem Details

input m * n grid “robot” starts at the top left of the grid grid[0][0] we need to get the robot to the bottom right of the grid[m-1][n-1] the robot can only move down or right return the number of possible unique paths that the robot can take to reach destination

💭What Were My Initial Thoughts?

1. Can it be broken into subproblems?
	- yes, there are x number of unique paths from any alement in the grid to the destination, 
	- we can use these to inform the number of unique paths from its neighbouring elements
2. Choose Top-Down vs Bottom-Up
	- starting from the destination and working toward the destination
	- bottom up approach

3. Define DP State
	- let dp[i][j] be the number of ways to reach the destination from the current position i,j
	- base case: dp[m-1][n-1] = 1 --> theres one way to stay at the destination

4. Transition Formula
	- dp[i][j] = dp[i+1][j] + dp[i][j+1]
	- fill the dp table bottom-up from m-1,n-1 to 0,0

💡 Explanation of Solution

We use dynamic programming to break the problem into smaller subproblems.

  1. Base Case:

    • The last row and last column are initialized to 1, because there is only one way to move from those positions to the destination (all right or all down).

  2. Transition Formula:

    • Each dp[i][j] is determined by adding the number of paths from the cell below (dp[i+1][j]) and the cell to the right (dp[i][j+1]).

  3. Bottom-Up Approach:

    • We start filling the dp table from the bottom-right (m-1, n-1) to the top-left (0,0).

  4. Final Answer:

    • dp[0][0] contains the number of unique paths from the start position to the destination.

⌛ Complexity Analysis

Time Complexity: O(m*n)
Space Complexity: O(m*n)

💻 Implementation of Solution

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1)); // Initialize all cells to 1
 
        // Fill the DP table bottom-up (excluding the last row and column)
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1]; // Down + Right
            }
        }
 
        return dp[0][0]; // Start position (0,0)
    }
};

Graph View