Unique Paths I (1D DP space Optmization)

62.Unique Paths

Dynamic Programming

Recursion

Matrix

Problem Statement:

A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. How many possible unique paths are there to reach the bottom-right corner?

Example:

Input:

m = 3, n = 7

→

Output:

28

Algorithm:

1. Bottom-up: Use 1D DP array for space optimization
2. Top-down: Use memoization with 2D array
3. Handle edge cases (last row/column)
4. Sum paths from right and bottom

Complexity:

Time: O(m*n) | Space: O(n) for bottom-up, O(m*n) for top-down

Java Solution:

// Bottom-up solution with space optimization
public int uniquePaths(int m, int n) {
    int[] dp = new int[n];  // 1D DP array
    
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            
            if (i == m - 1 && j == n - 1)  // Bottom-right corner
                dp[j] = 1;
            else if (i == m - 1)  // Bottom row
                dp[j] = dp[j + 1];
            else if (j == n - 1)  // Right column
                dp[j] = dp[j];
            
            if (i != m - 1 && j != n - 1)  // Middle cells
                dp[j] = dp[j + 1] + dp[j];  // Right + Down paths
        }
    }

    return dp[0];
}

// Top-down solution with memoization
public int uniquePathsTopDown(int m, int n) {
    int[][] dp = new int[m][n];
    
    for (int[] a : dp) 
        Arrays.fill(a, -1);  // Initialize with -1

    return countPaths(m - 1, n - 1, dp);
}

private int countPaths(int m, int n, int[][] dp) {
    if (m < 0 || n < 0)  // Out of bounds
        return 0;

    if (dp[m][n] != -1)  // Return cached result
        return dp[m][n];
    
    if (m == 0 && n == 0)  // Reached start
        return 1;

    int ans = countPaths(m - 1, n, dp) + countPaths(m, n - 1, dp);
    dp[m][n] = ans;  // Cache result
    return ans;
}

Python Solution:

def uniquePaths(self, m: int, n: int) -> int:
    dp = [0] * n  # 1D DP array
    
    for i in range(m-1, -1, -1):
        for j in range(n-1, -1, -1):
            if i == m-1 and j == n-1:
                dp[j] = 1
            elif i == m-1:
                dp[j] = dp[j+1]
            elif j != n-1:
                dp[j] = dp[j+1] + dp[j]
    
    return dp[0]

# Top-down solution
def uniquePathsTopDown(self, m: int, n: int) -> int:
    @lru_cache(None)
    def dfs(i: int, j: int) -> int:
        if i < 0 or j < 0:
            return 0
        if i == 0 and j == 0:
            return 1
        return dfs(i-1, j) + dfs(i, j-1)
    
    return dfs(m-1, n-1)

C++ Solution:

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n);  // 1D DP array
        
        for(int i = m-1; i >= 0; i--) {
            for(int j = n-1; j >= 0; j--) {
                if(i == m-1 && j == n-1)
                    dp[j] = 1;
                else if(i == m-1)
                    dp[j] = dp[j+1];
                else if(j != n-1)
                    dp[j] = dp[j+1] + dp[j];
            }
        }
        
        return dp[0];
    }
    
    int uniquePathsTopDown(int m, int n) {
        vectorint>> dp(m, vector<int>(n, -1));
        return countPaths(m-1, n-1, dp);
    }
    
private:
    int countPaths(int m, int n, vectorint>>& dp) {
        if(m < 0 || n < 0) return 0;
        if(dp[m][n] != -1) return dp[m][n];
        if(m == 0 && n == 0) return 1;
        
        return dp[m][n] = countPaths(m-1, n, dp) + countPaths(m, n-1, dp);
    }
};