62. Unique Paths

There is a robot on an?m x n?grid. The robot is initially located at the?top-left corner?(i.e.,?grid[0][0]). The robot tries to move to the?bottom-right corner?(i.e.,?grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers?m?and?n, return?the number of possible unique paths that the robot can take to reach the bottom-right corner.

思路：以下分析摘自https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html#%E6%80%9D%E8%B7%AF

樹的深度是m+n+1，二叉樹的節(jié)點(diǎn)個數(shù)是2^(m+n+1)，DFS需要遍歷整個二叉樹，算法復(fù)雜度就是O(2^(m + n - 1) - 1)，這是指數(shù)級別的復(fù)雜度。

機(jī)器人從(0 , 0) 位置出發(fā)，到(m - 1, n - 1)終點(diǎn)。

按照動規(guī)五部曲來分析：

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i][j] ：表示從（0 ，0）出發(fā)，到(i, j) 有dp[i][j]條不同的路徑。

2. 確定遞推公式

想要求dp[i][j]，只能有兩個方向來推導(dǎo)出來，即dp[i - 1][j] 和 dp[i][j - 1]。

此時在回顧一下 dp[i - 1][j] 表示啥，是從(0, 0)的位置到(i - 1, j)有幾條路徑，dp[i][j - 1]同理。

那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因?yàn)閐p[i][j]只有這兩個方向過來。

3. dp數(shù)組的初始化

如何初始化呢，首先dp[i][0]一定都是1，因?yàn)閺?0, 0)的位置到(i, 0)的路徑只有一條，那么dp[0][j]也同理。

4. 確定遍歷順序

這里要看一下遞推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是從其上方和左方推導(dǎo)而來，那么從左到右一層一層遍歷就可以了。

這樣就可以保證推導(dǎo)dp[i][j]的時候，dp[i - 1][j] 和 dp[i][j - 1]一定是有數(shù)值的。

5. 舉例推導(dǎo)dp數(shù)組

數(shù)論方法：

可以看出一共m，n的話，無論怎么走，走到終點(diǎn)都需要 m + n - 2 步。

在這m + n - 2 步中，一定有 m - 1 步是要向下走的，不用管什么時候向下走。

那么有幾種走法呢？ 可以轉(zhuǎn)化為，給你m + n - 2個不同的數(shù)，隨便取m - 1個數(shù)，有幾種取法。

那么這就是一個組合問題了。

所以以下就是可走的path的個數(shù)：

遞歸法：

def Solution():
    def uniquePaths(self, m, n):
        if m == 1 or n == 1:
            return 1
        return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n-1)

動態(tài)規(guī)劃法：

class Solution(object):
    def uniquePaths(self, m, n):
        dp = [[0] * n] * m
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

注意！之前習(xí)慣了numpy，總是直接dp[:,0] = 1，這樣在list里是不對的。

63. Unique Paths II

如果有障礙物的話，之后的路就不通了，在設(shè)置初始狀態(tài)和更新狀態(tài)的時候都要對應(yīng)改動。

具體分析見此鏈接代碼隨想錄文章來源地址http://www.zghlxwxcb.cn/news/detail-808194.html

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid[0][0] == 1)
            return 0;
        vector<int> dp(obstacleGrid[0].size());
        for (int j = 0; j < dp.size(); ++j)
            if (obstacleGrid[0][j] == 1)
                dp[j] = 0;
            else if (j == 0)
                dp[j] = 1;
            else
                dp[j] = dp[j-1];

        for (int i = 1; i < obstacleGrid.size(); ++i)
            for (int j = 0; j < dp.size(); ++j){
                if (obstacleGrid[i][j] == 1)
                    dp[j] = 0;
                else if (j != 0)
                    dp[j] = dp[j] + dp[j-1];
            }
        return dp.back();
    }
};

到了這里，關(guān)于算法練習(xí)Day30 （Leetcode/Python-動態(tài)規(guī)劃）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！