LeetCode Unique Paths I and II: DP with Memory Optimization

Overview

LeetCode Unique Paths I and II could be solved by dynamic programming with memory optimization. We can treat problem I as a combinations problem as well.

LeetCode Unique Paths I and II:

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and `` respectively in the grid.

For example,

There is one obstacle in the middle of a 3×3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

Analysis: Dynamic Programming

Quite simple and straightforward problem using dynamic programming, for the problem without any obstacles the recursive formula is:

dp[m][n] = dp[m][n-1] + dp[m-1][n] where dp[m][n] denotes the number of unique paths

For the problem with obstacles, the recursive formula is essentially the same:

          dp[m][n] = dp[m][n-1] + dp[m-1][n]  if the cell at the position (m, n) is empty

dp[m][n] = 0 if the cell at the position (m, n) is occupied by an obstacle

Implementation Detail Memory Optimization

1) The direct implementation of the Unique Path I problem would be the following using m * n dp array, and it is accepted by LeetCode OJ to pass this Unique:

int uniquePaths(int m, int n) {
    if (m < 1 || n < 1)
        return 0;

    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];
}

2) Note the value of dp[i][j] only depends on the previous two grids, we could optimize the memory and make it O(max(m, n)) cost as the following code does:

int uniquePaths(int m, int n) {
    if (m < 1 || n < 1)
        return 0;

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

3) Similarly, for the second Unique Path II problem, the code after memory optimization and could be accepted by the LeetCode OJ is as follows:

int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
    int m = obstacleGrid.size();
    if (m < 1)
        return 0;
    int n = obstacleGrid[0].size();

    vector<int> dp(n + 1, 0);
    dp[1] = obstacleGrid[0][0] == 1 ? 0 : 1;

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) {
            dp[j] = (1 == obstacleGrid[i-1][j-1] ? 0 : dp[j] + dp[j-1]);
        }

    return dp[n];
}

4) For the Unique Path I problem, we can also treat it as a mathematical combinations problem. So we need to take totally m + n – 2 steps to reach the final grid at (m, n), and among the m + n – 2 steps there are m – 1 steps towards down and n – 1 steps towards right direction. So the number of such different paths is just the answer to the problem of that select n – 1 steps towards right from the m + n – 2 steps. So mathematically, the results would be C(m+n-2, n -1) and it could be directly calculated by multiplication. The overflow issue should be taken care of though.

5) For the Unique Path I and II problem there actually exist O(1) Space solution by directly modifying the input grid, the reason we can achieve this is that after say using grid[i-1][j] or grid[i][j-1], this grid actually is useless which means, we will not access it anymore in the future thus it could be modified.

I finish the discussion here for now, and you are very welcome to leave any comments!

Summary

LeetCode Unique Paths I and II could be solved by dynamic programming with memory optimization. We can treat problem I as a combinations problem as well.

Written on February 3, 2013