Unique paths in a grid

Count the routes from the top-left to the bottom-right corner when you may only move right or down.

Time O(rows × cols)Space O(rows × cols)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

You can only arrive at a cell from above or from the left. So the number of routes into a cell is the sum of the routes into those two neighbours.

Code

C++PythonC#

int uniquePaths(int rows, int cols) {
    vector<vector<int>> dp(rows, vector<int>(cols));
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            dp[r][c] = r == 0 || c == 0
                ? 1
                : dp[r - 1][c] + dp[r][c - 1];
    return dp[rows - 1][cols - 1];
}

def unique_paths(rows: int, cols: int) -> int:
    dp = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if r == 0 or c == 0:
                dp[r][c] = 1
            else:
                dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[rows - 1][cols - 1]

public static int UniquePaths(int rows, int cols) {
    var dp = new int[rows, cols];
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            dp[r, c] = r == 0 || c == 0
                ? 1
                : dp[r - 1, c] + dp[r, c - 1];
    return dp[rows - 1, cols - 1];
}

Tips

The top row and left column have exactly one route each: straight along the edge.
Add obstacles by setting blocked cells to 0. The rest of the logic is unchanged.

In the .NET library

The nested conditional operator keeps the edge case and the general case in one assignment. Split it into an if/else if you find that easier to read.