聊聊DP入門之不同路徑
一個機器人位于一個 m x n 網格的左上角 (起始點在下圖中標記為 “Start” )。
機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角(在下圖中標記為 “Finish” )。
問總共有多少條不同的路徑?
示例 1：
- 輸入：m = 3, n = 7
- 輸出：28
示例 2：
- 輸入：m = 2, n = 3
- 輸出：3
解釋：從左上角開始，總共有 3 條路徑可以到達右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 3：
- 輸入：m = 7, n = 3
- 輸出：28
示例 4：
- 輸入：m = 3, n = 3
- 輸出：6
提示：
- 1 <= m, n <= 100
- 題目數據保證答案小于等于 2 * 10^9
思路
深搜
這道題目，剛一看最直觀的想法就是用圖論里的深搜，來枚舉出來有多少種路徑。
注意題目中說機器人每次只能向下或者向右移動一步，那么其實機器人走過的路徑可以抽象為一顆二叉樹，而葉子節點就是終點!
如圖舉例：
不同路徑
此時問題就可以轉化為求二叉樹葉子節點的個數，代碼如下：
- 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; // 找到一種方法，相當于找到了葉子節點
- 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);
- }
- };
大家如果提交了代碼就會發現超時了!
來分析一下時間復雜度，這個深搜的算法，其實就是要遍歷整個二叉樹。
這顆樹的深度其實就是m+n-1(深度按從1開始計算)。
那二叉樹的節點個數就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍歷了整個滿二叉樹(其實沒有遍歷整個滿二叉樹，只是近似而已)
所以上面深搜代碼的時間復雜度為，可以看出，這是指數級別的時間復雜度，是非常大的。
動態規劃
機器人從(0 , 0) 位置出發，到(m - 1, n - 1)終點。
按照動規五部曲來分析：
確定dp數組(dp table)以及下標的含義
dp[i][j] ：表示從(0 ，0)出發，到(i, j) 有dp[i][j]條不同的路徑。
確定遞推公式
想要求dp[i][j]，只能有兩個方向來推導出來，即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數組的初始化
如何初始化呢，首先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]都是從其上方和左方推導而來，那么從左到右一層一層遍歷就可以了。
這樣就可以保證推導dp[i][j]的時候，dp[i - 1][j] 和 dp[i][j - 1]一定是有數值的。
舉例推導dp數組
如圖所示：
不同路徑
以上動規五部曲分析完畢，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];
- }
- };
時間復雜度：
空間復雜度：
其實用一個一維數組(也可以理解是滾動數組)就可以了，但是不利于理解，可以優化點空間，建議先理解了二維，在理解一維，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];
- }
- };
時間復雜度：
空間復雜度：
數論方法
在這個圖中，可以看出一共m，n的話，無論怎么走，走到終點都需要 m + n - 2 步。
不同路徑
在這m + n - 2 步中，一定有 m - 1 步是要向下走的，不用管什么時候向下走。
那么有幾種走法呢?可以轉化為，給你m + n - 2個不同的數，隨便取m - 1個數，有幾種取法。
那么這就是一個組合問題了。
那么答案，如圖所示：
不同路徑
求組合的時候，要防止兩個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;
- }
- };
時間復雜度：
空間復雜度：
計算組合問題的代碼還是有難度的，特別是處理溢出的情況!
總結
本文分別給出了深搜，動規，數論三種方法。
深搜當然是超時了，順便分析了一下使用深搜的時間復雜度，就可以看出為什么超時了。
然后在給出動規的方法，依然是使用動規五部曲，這次我們就要考慮如何正確的初始化了，初始化和遍歷順序其實也很重要!
