一個機(jī)器人位于一個 m x n 網(wǎng)格的左上角 (起始點在下圖中標(biāo)記為 “Start” )。

機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角(在下圖中標(biāo)記為 “Finish” )。

問總共有多少條不同的路徑?

示例 1：

• 輸入：m = 3, n = 7
• 輸出：28

示例 2：

• 輸入：m = 2, n = 3
• 輸出：3

解釋：從左上角開始，總共有 3 條路徑可以到達(dá)右下角。

• 向右 -> 向右 -> 向下
• 向右 -> 向下 -> 向右
• 向下 -> 向右 -> 向右

示例 3：

• 輸入：m = 7, n = 3
• 輸出：28

示例 4：

• 輸入：m = 3, n = 3
• 輸出：6

提示：

• 1 <= m, n <= 100
• 題目數(shù)據(jù)保證答案小于等于 2 * 10^9

思路

深搜

這道題目，剛一看最直觀的想法就是用圖論里的深搜，來枚舉出來有多少種路徑。

注意題目中說機(jī)器人每次只能向下或者向右移動一步，那么其實機(jī)器人走過的路徑可以抽象為一顆二叉樹，而葉子節(jié)點就是終點!

如圖舉例：

不同路徑

此時問題就可以轉(zhuǎn)化為求二叉樹葉子節(jié)點的個數(shù)，代碼如下：

class Solution { 
private: 
    int dfs(int i, int j, int m, int n) { 
        if (i > m || j > n) return 0; // 越界了 
        if (i == m && j == n) return 1; // 找到一種方法，相當(dāng)于找到了葉子節(jié)點 
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n); 
    } 
public: 
    int uniquePaths(int m, int n) { 
        return dfs(1, 1, m, n); 
    } 
}; 

大家如果提交了代碼就會發(fā)現(xiàn)超時了!

來分析一下時間復(fù)雜度，這個深搜的算法，其實就是要遍歷整個二叉樹。

這顆樹的深度其實就是m+n-1(深度按從1開始計算)。

那二叉樹的節(jié)點個數(shù)就是 2^(m + n - 1) - 1?？梢岳斫馍钏训乃惴ň褪潜闅v了整個滿二叉樹(其實沒有遍歷整個滿二叉樹，只是近似而已)

所以上面深搜代碼的時間復(fù)雜度為，可以看出，這是指數(shù)級別的時間復(fù)雜度，是非常大的。

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

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

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

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

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

確定遞推公式

想要求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]，因為dp[i][j]只有這兩個方向過來。

dp數(shù)組的初始化

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

所以初始化代碼為：

for (int i = 0; i < m; i++) dp[i][0] = 1; 
for (int j = 0; j < n; j++) dp[0][j] = 1; 

確定遍歷順序

這里要看一下遞歸公式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ù)值的。

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

如圖所示：

不同路徑

以上動規(guī)五部曲分析完畢，C++代碼如下：

class Solution { 
public: 
    int uniquePaths(int m, int n) { 
        vector<vector<int>> dp(m, vector<int>(n, 0)); 
        for (int i = 0; i < m; i++) dp[i][0] = 1; 
        for (int j = 0; j < n; j++) dp[0][j] = 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]; 
    } 
}; 

時間復(fù)雜度：

空間復(fù)雜度：

其實用一個一維數(shù)組(也可以理解是滾動數(shù)組)就可以了，但是不利于理解，可以優(yōu)化點空間，建議先理解了二維，在理解一維，C++代碼如下：

class Solution { 
public: 
    int uniquePaths(int m, int n) { 
        vector<int> dp(n); 
        for (int i = 0; i < n; i++) dp[i] = 1; 
        for (int j = 1; j < m; j++) { 
            for (int i = 1; i < n; i++) { 
                dp[i] += dp[i - 1]; 
            } 
        } 
        return dp[n - 1]; 
    } 
}; 

時間復(fù)雜度：

空間復(fù)雜度：

數(shù)論方法

在這個圖中，可以看出一共m，n的話，無論怎么走，走到終點都需要 m + n - 2 步。

不同路徑

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

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

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

那么答案，如圖所示：

不同路徑

求組合的時候，要防止兩個int相乘溢出! 所以不能把算式的分子都算出來，分母都算出來再做除法。

例如如下代碼是不行的。

class Solution { 
public: 
    int uniquePaths(int m, int n) { 
        int numerator = 1, denominator = 1; 
        int count = m - 1; 
        int t = m + n - 2; 
        while (count--) numerator *= (t--); // 計算分子，此時分子就會溢出 
        for (int i = 1; i <= m - 1; i++) denominator *= i; // 計算分母 
        return numerator / denominator; 
    } 
}; 

需要在計算分子的時候，不斷除以分母，代碼如下：

class Solution { 
public: 
    int uniquePaths(int m, int n) { 
        long long numerator = 1; // 分子 
        int denominator = m - 1; // 分母 
        int count = m - 1; 
        int t = m + n - 2; 
        while (count--) { 
            numerator *= (t--); 
            while (denominator != 0 && numerator % denominator == 0) { 
                numerator /= denominator; 
                denominator--; 
            } 
        } 
        return numerator; 
    } 
}; 

時間復(fù)雜度：

空間復(fù)雜度：

計算組合問題的代碼還是有難度的，特別是處理溢出的情況!

總結(jié)

本文分別給出了深搜，動規(guī)，數(shù)論三種方法。

深搜當(dāng)然是超時了，順便分析了一下使用深搜的時間復(fù)雜度，就可以看出為什么超時了。

然后在給出動規(guī)的方法，依然是使用動規(guī)五部曲，這次我們就要考慮如何正確的初始化了，初始化和遍歷順序其實也很重要!