Back to solutions

Unique Paths

MediumDynamic Programming

Count the paths a robot can take from the top-left to the bottom-right of an m x n grid moving only right or down.

Open problem
Constraints
  • 1 <= m, n <= 100

Row-compressed DP

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

The number of paths to a cell is the sum of paths from above and from the left. Keep a single row and update it left to right for each grid row.

#include <bits/stdc++.h>
using namespace std;

int uniquePaths(int m, int n) {
    vector<int> row(n, 1);
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            row[j] += row[j - 1];
    return row[n - 1];
}