Leetcode题解（1）：动态规划
第一眼看到这道题就联想到了离散数学里的排列的相关知识，从而可以很容易的得出排列数为 $C(m+n-2,m-1)$ 或者 $C(m+n-2,n-1)$，可以直接利用该公式进行计算。但问题是阶乘的增长量级过大，很快就产生了溢出的问题，这时可以通过使用 $BigInteger$ 类型对象解决。
虽然问题解决了，但显然这种偏暴力方式的解法不是我们的目的，因此我们还要寻找另一种解法。通过观察题目，我们可以很明显的发现：由于只能右移或者下移，因此到达每一块方格的路径数（不包括第一行和第一列） = 到达其左边方格的路径数 + 到达其上边方格的路径数。以此规律，我们可以运用动态规划来解决该问题。
首先先设
int[][] dp = new int[m][n];
dp数组为二维数组，储存到达每个方格的路径数。由于达到第一列和第一行中所有方格的路径数有且仅有一条，因此可以
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int i = 1; i < n; i++) dp[0][i] = 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];
在此，无论是按行还是按列，结果都是一样的。最后 $dp[m - 1][n - 1]$ 即为答案。将上述代码合并起来即为：
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int i = 1; i < n; i++) dp[0][i] = 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];
}
}
到此为止的解法已经很好了，但仍有优化空间。我们可以从一些极端情况开始重新考虑。
在相同条件下考虑一个 $1 \times n$ 的网格。显然路径有且只有一条。对此构造数组储存路径数，暂且将其命名为 $dp1[n]$，其中每个元素均为 $1$。在 $1 \times n$ 的基础上，我们再考虑一个 $2 \times n$ 的网格，将其分为两列，显然第一列即为之前讨论的 $1 \times n$ 网格，我们用 $dp1[n]$ 进行储存，第二列我们用 $dp2[n]$ 进行储存。再利用之前讨论出来的规律，我们可以知道对于第二列中的每个方格，其路径数等于左边以及上边方格路径数之和，其左边方格的路径数之和储存在 $dp1[n]$ 中，上边方格的路径数储存在 $dp2[n]$ 之中，因此对于第二列的每个方格，我们可以用动态规划进行赋值，如下所示：
dp2[0] = 1; //第一行路径数为1
for (int i = 1; i < n; i++)
dp2[i] = dp1[i] /*左边方格路径数*/ + dp2[i - 1]; /*上边方格路径数*/
以此，我们可以将网格继续扩大，从 $2 \times n$ 直到 $m \times n$。利用代码比较直观的实现思路为设置两个数组，大小均为 $n$，其中一个储存当前列的路径数，记为 $cur[n]$，另一个储存之前列的路径数，记为 $pre[n]$。动态规划过程循环可以改为：
for (int i = 1; i < m; i++) {
for (int j = 1; i < n; j++)
cur[j] = pre[j] + cur[j - 1];
pre = cur.clone();
}
空间复杂度由原来的 $O(m \times n)$ 降低至 $O(2n)$，从而大大减小，不过还可以更小。重新审视我们的思路，可以发现，利用 $pre$ 储存前一列的路径数是不必要的，因为在动态规划过程中， $pre[j]$ 实际上与未改变前的 $cur[j]$ 是相等的，即前一列相同行上的数据实际上本就储存在当前位置上，因此，可以再进一步改进循环：
for (int i = 1; i < m; i++)
for (int j = 1; i < n; j++)
cur[j] += cur[j - 1];
至此，空间复杂度进一步缩小为 $O(n)$。最终经过优化后的代码如下：
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[j] += dp[j - 1];
return dp[n - 1];
}
}
最后进行总结，此题可以用排列数进行计算，也可以运用动态规划进行计算，使用动态规划方法，时间复杂度为 $O(m \times n)$，空间复杂度可以优化至 $O(n)$。
在解决完这道题之后，我们可以再来看一道相似的题目。
很明显，这道题就不能直观的由排列数得出答案了，因为加入了障碍，即不可达方块。但仍然可以通过动态规划得出答案。
我们再从极端情况开始考虑。考虑一个 $1 \times n$ 的网格，用 $dp[n]$ 储存路径数。显然，当 $obstacleGrid[0]$ 里面的元素都为 $0$ 时，$dp[n]$ 内的元素都为 $0$ ；而当 $obstacleGrid[0]$ 里面存在一个 $1$ 时，即当 $obstacleGrid[0][i]$ 为 $1$ 时，在 $dp[n]$ 中，所有地址小于 $i$ 的元素均为 $1$ ，大于 $i$ 的元素均为 $0$ 。由此可以进行如下初始化：
int n = obstacle[0].length;
int[] dp = new int[n];
for (int i = 0; i < n; i++)
if (obstacle[0][i] == 0) dp[i] = 1;
else break;
从而可以得出 $1 \times n$ 网格情况下的答案。再将其扩至 $2 \times n$ 网格，将其分为两列，第一列与上例相同。在对第二列进行规划时，可以发现，如果存在 $obstacleGrid[1][i]$ 为 $0$ ，那么 $dp[i]$ 也将为 $0$ ；若不为零。则与上一题相同，因此只需稍加修改前一题的代码即可。另外，由于上一题中第一行中所有元素均为 $1$ 而本题不一定，所以在对每列进行规划之前都要对 $dp[0]$ 进行一次判断和赋值。经过修改后的完整代码如下：
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
for (int i = 0; i < n; i++)
if (obstacleGrid[i][0] == 1) dp[i] = 1;
else break;
for (int i = 1; i < m; i++) {
if (obstacleGrid[i][0] == 1) dp[0] = 0;
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) dp[j] = 0;
else dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
}
时间复杂度 $O(m \times n)$，空间复杂度 $O(n)$，与上题相同。