聊聊DP入門(mén)之不同路徑

作者：程序員Carl 2022-01-04 11:31:15

本文分別給出了深搜，動(dòng)規(guī)，數(shù)論三種方法。深搜當(dāng)然是超時(shí)了，順便分析了一下使用深搜的時(shí)間復(fù)雜度，就可以看出為什么超時(shí)了。然后在給出動(dòng)規(guī)的方法，依然是使用動(dòng)規(guī)五部曲，這次我們就要考慮如何正確的初始化了，初始化和遍歷順序其實(shí)也很重要!

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

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

問(wèn)總共有多少條不同的路徑?

示例 1：

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

示例 2：

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

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

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

示例 3：

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

示例 4：

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

提示：

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

思路

深搜

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

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

如圖舉例：

不同路徑

此時(shí)問(wèn)題就可以轉(zhuǎn)化為求二叉樹(shù)葉子節(jié)點(diǎn)的個(gè)數(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é)點(diǎn) 
        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); 
    } 
};

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

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

這顆樹(shù)的深度其實(shí)就是m+n-1(深度按從1開(kāi)始計(jì)算)。

那二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍歷了整個(gè)滿二叉樹(shù)(其實(shí)沒(méi)有遍歷整個(gè)滿二叉樹(shù)，只是近似而已)

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

動(dòng)態(tài)規(guī)劃

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

按照動(dòng)規(guī)五部曲來(lái)分析：

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

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

確定遞推公式

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

此時(shí)在回顧一下 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]只有這兩個(gè)方向過(guò)來(lái)。

dp數(shù)組的初始化

如何初始化呢，首先dp[i][0]一定都是1，因?yàn)閺?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)而來(lái)，那么從左到右一層一層遍歷就可以了。

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

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

如圖所示：

不同路徑

以上動(dòng)規(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]; 
    } 
};

時(shí)間復(fù)雜度：

空間復(fù)雜度：

其實(shí)用一個(gè)一維數(shù)組(也可以理解是滾動(dòng)數(shù)組)就可以了，但是不利于理解，可以優(yōu)化點(diǎn)空間，建議先理解了二維，在理解一維，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]; 
    } 
};

時(shí)間復(fù)雜度：

空間復(fù)雜度：

數(shù)論方法

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

不同路徑

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

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

那么這就是一個(gè)組合問(wèn)題了。

那么答案，如圖所示：

不同路徑

求組合的時(shí)候，要防止兩個(gè)int相乘溢出! 所以不能把算式的分子都算出來(lái)，分母都算出來(lái)再做除法。

例如如下代碼是不行的。

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--); // 計(jì)算分子，此時(shí)分子就會(huì)溢出 
        for (int i = 1; i <= m - 1; i++) denominator *= i; // 計(jì)算分母 
        return numerator / denominator; 
    } 
};

需要在計(jì)算分子的時(shí)候，不斷除以分母，代碼如下：

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; 
    } 
};