Leetcode题解(1):动态规划

原题地址:Problem 62

参考题解

       第一眼看到这道题就联想到了离散数学里的排列的相关知识,从而可以很容易的得出排列数为 $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)$。
       在解决完这道题之后,我们可以再来看一道相似的题目。


原题地址:Problem 63

       很明显,这道题就不能直观的由排列数得出答案了,因为加入了障碍,即不可达方块。但仍然可以通过动态规划得出答案。
       我们再从极端情况开始考虑。考虑一个 $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)$,与上题相同。