[LeetCode] Unique Paths

Well, there is a nice and succinct solution to this problem using math skills. However, personally I guess it would be safer to use DP in a coding interview since it is more likely to be what the problem desires from us. Of course, the math solution is very insightful and clever and would be a nice plus if you could give it in an interview.

Since the robot can only move right and down, when it arrives at a point, there are only two possibilities:

1. It arrives at that point from above (moving down to that point);
2. It arrives at that point from left (moving right to that point).

Thus, we have the following state equations: suppose the number of paths to arrive at a point (i, j) is denoted as P[i][j], then it is easily concluded that P[i][j] = P[i - 1][j] + P[i][j - 1]. Of course, some boundary conditions (the point has no points above it or left to it) need to be handled.

The boundary conditions occur at the leftmost column (no points left to it, P[i][j - 1] does not exist) and the uppermost row (no points above it, P[i - 1][j] does not exist). These conditions can be handled by initialization (pre-processing). We simply initialize P[0][j] = 1 and P[i][0] = 1 for all valid i and j. Note that the initial value is 1 instead of 0!

Now we can easily come to the following (unoptimized) solution.

1     int uniquePaths(int m, int n) {
2         vector<vector<int> > path(m, vector<int> (n, 1));
3         for (int i = 1; i < m; i++)
4             for (int j = 1; j < n; j++)
5                 path[i][j] = path[i - 1][j] + path[i][j - 1];
6         return path[m - 1][n - 1];
7     }

As can be seen, the above solution runs in O(n^2) time and costs O(n^2) space. However, you may have observed that each time when we update path[i][j], we only need the point above it (at the same column with it) and the point left to it (at the left column to it), which means that it is enough to maintain only two columns (the current column and the previous left column). So the above solution can be optimized to O(n) space complexity as follows.

 1     int uniquePaths(int m, int n) {
 2         vector<int> pre(m, 1);
 3         vector<int> cur(m, 1);
 4         for (int j = 1; j < n; j++) {
 5             for (int i = 1; i < m; i++)
 6                 cur[i] = cur[i - 1] + pre[i];
 7             pre = cur;
 8         }
 9         return cur[m - 1];
10     }

[LeetCode] Unique Paths

原文：http://www.cnblogs.com/jcliBlogger/p/4548046.html