2020-12-9 不同路徑

題目

解題思路

法一：暴力回溯

看到題目給的示意圖（一個迷宮），首先想到的就是回溯法，使用一個變量

count

來記錄路徑的條數，一旦找到一條路徑

count

便加一，詳情看代碼。

class Solution {
public:
    int uniquePaths(int m, int n) {
        int count = 0;
        int a = 1, b = 1;	// 初始位置為(1,1)
        findPathCount(count, a, b, m, n);
        return count;
    }

    void findPathCount(int &count, int a, int b, int m, int n){
        if (a > m || b > n)	// 超出迷宮的範圍便直接退出
            return ;
            
        if (a == m && b == n){	// 到達終點count加1
            count++;
            return ;
        }
		
        findPathCount(count, a+1, b, m, n);	// 往下走&往右走
        findPathCount(count, a, b+1, m, n);
    }
};
           

由于該方法時間複雜度過高，送出後未能通過。

法二：動态規劃

經分析，對于迷宮中除了上邊界與左邊界的任一格(left(i,j

ight))，到達該格可能的路徑條數(dp[i][j]=dp[i-1][j]+dp[i][j-1]) ，而從起點出發到達上邊界或左邊界的任意一格的路徑數量均能為1，因為機器人隻能往下走或往右走。是以可使用動态規劃來解決該問題。詳情看代碼。

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

時間複雜度：(O(mn))

空間複雜度：(O(mn))

法三：組合數學

從左上角到右下角的過程中，我們需要向右移動

n-1

次，向下移動

m-1

次，共移動

m+n-2

次。是以路徑的總數，就等于從

m+n-2

次移動中選擇

m-1

次向下移動的方案數，即組合數：

[C_{m+n-2}^{m-1}= binom{m+n-2}{m-1}=frac{(m+n-2)(m+n-3)...n}{(m-1)!}=frac{(m+n-2)!}{(m-1)!(n-1)!}

]

兩種解法:

• 直接調用組合數的API；
• 自己寫代碼計算；

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return ans;
    }
};
           

送出結果