Unique Paths（动态规划求解）

题目

题目来源：LeetCode

1. 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?
   Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
2. Right -> Right -> Down
3. Right -> Down -> Right
4. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

5. 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).
   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 0 respectively in the grid.
   Note: m and n will be at most 100.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

分析

题目2是题目1的改进。在题目1中，实际上是给出一个m * n的矩阵，机器人只能向右走或者是向左走。求机器人从右上角到左下角，一共有多少种走法。在题目2中，给出的m * n矩阵多了一些障碍物。机器人无法从障碍物上面通过。

求解思路

先从题目1入手，机器人只能有两种走法，要么向右，要么向下。那么，若机器人现在在位置(i, j)上面，那么，它只能来源于(i - 1, j)或者是(i, j - 1)。若使用F(i, j)表示机器人走到位置(i, j)的可能走法，那么F(i, j) = F(i - 1, j) + F(i, j - 1)。
此外F(0, j) = F(0, j - 1)和 F(i, 0) = F(i - 1, 0)（若当前位置再最左边或者最上面，只有一种来源）。
对于题目2，相较于题目1，若某个位置为障碍物，则其走法为0，因为没有一种走法能够到达该位置。当某个位置的一个来源为障碍物时，与另外一个来源的走法相同，因为此时该位置只能来源于特定的位置。此时计算方法不变仍然为F(i, j) = F(i - 1, j) + F(i, j - 1)（因为其中一个为0。若两个来源都为障碍物，结果为0，该式子仍然适用）。

代码如下

简单递归

对于题目1，由于我们在上面已经得出了状态转移方程F(i, j) = F(i - 1, j) + F(i, j - 1)，因此可以直接使用递归求解。但是，使用该方法求解时，时间复杂度为O(2^n)，空间复杂度为O(1)。当n, m过大时，会超时。
对于题目2，只需要在题目1的基础上修改即可，由于使用该方法，两个题目都会超时，故此只给出题目1的简单递归代码。

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
        	return 1;
		}
		return uniquePaths(m - 1, n) + uniquePaths(m, n-1);
    }
};

动态规划

由于使用简单递归时，时间复杂度过高。因此，我们可以从小到大，直接从第一个格子开始计算。使用一个二维数组存储每一个结果。右下角那个格子的结果就是我们的最终结果。
使用该方法，时间复杂度为O(m * n)，空间复杂度为O(m * n)
题目1的代码：

class Solution {
public:
    // 题目1
    int uniquePaths(int m, int n) {
		int** array = new int*[m];  // 用于存储中间结果
		for (int i = 0; i < m; i++) {
			array[i] = new int[n];
		}
		for (int i = 0; i < m; i++) {
			array[i][0] = 1;
		}
		for (int i = 0; i < n; i++) {
			array[0][i] = 1;
		}
		// 双重循环，计算出最终的结果
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				array[i][j] = array[i - 1][j] + array[i][j - 1];
			}
		}
		return array[m - 1][n - 1];
    }
};

题目2的代码：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    	int m = obstacleGrid.size();
    	int n = obstacleGrid[0].size();
		int flag = 1;
		int** array = new int*[m];  // 用于存储中间结果
		for (int i = 0; i < m; i++) {
			array[i] = new int[n];
		}
		for (int i = 0; i < m; i++) {  // 最左边的格子的情况
			if (obstacleGrid[i][0] == 1) {  // 若有障碍物，向下的格子都无法达到
				flag = 0;
			}
			array[i][0] = flag;
		}
		flag = 1;
		for (int i = 0; i < n; i++) {  // 最右边的格子的情况
			if (obstacleGrid[0][i] == 1) {  // 若有障碍物，向右的格子都无法达到
				flag = 0;
			}
			array[0][i] = flag;
		}
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				if (obstacleGrid[i][j] == 1) {
					array[i][j] = 0;
				} else {
					array[i][j] = array[i - 1][j] + array[i][j - 1];
				}
			}
		}
		return array[m - 1][n - 1];
    }
};

改进

实际上，并不需要存储所有格子的走法。只需要存储一行即可。新的一行可以直接由当前行得到。第i行第一个格子的走法与第i - 1行的第一个格子的走法相同。第i行的第j个格子可以由第i - 1行的第j个格子加上第i行的第j - 1个格子得到。由于我们是从左到右，从上到下计算，此时F(i - 1, j)和F(i, j - 1)都已经知道了。使用该方法，时间复杂度仍然为O(m * n)，空间复杂度减少为O(n)。
下面给出题目1的改进代码，题目2的改进与1的类似，就不给出了。

class Solution {
public:
    int uniquePaths(int m, int n) {
		int *array = new int[n];
		int** array = new int*[m];
		for (int i = 0; i < n; i++) {
			array[0][i] = 1;
		}
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {  // 当 j = 0时，array[j]不变。
				array[j] = array[j - 1] + array[j]; 
			}
		}
		return array[n - 1];
    }
};