LeetCode 62. Unique Paths [Medium] [C++] 解題筆記

這題給定一個 m x n 的 grid map，要我們求從左上走到右下只能往右或往下走的話，總共有幾種走法。

EX:

        m = 7, n = 3  

Ans: 28

想法:

        

        這個問題其實大家都學過，忘了是國中還是高中數學會學到的 "同物排列" 的問題，這個問題可以看成是一串向右,向下箭頭的同物排列數，因為如這個例子從左上走到右下(不能往回走）必定需要６次向右走，２次向下走，因此答案是　8! / 6!*2! = 28。

除了上述的數學解法以外，這題還可以利用 DP 來求解，對於每一個位置 P 而言，要能夠走到 P 必定是從 P 的上方或者是左方走過來，因此從左上角走到 P 的方法數就等同於從左上角走到 P 左方一格的方法數加上從左上角走到 P 上方一格的方法數，依此類推到右下角就可以得到從左上到右下的總方法數。

另外利用 DP 實做此題時最直覺的方法是建立一個 m x n 的二維陣列來紀錄每個位置的方法數，

但如果仔細觀察會發現對於每個位置 P 而言只需要知道他的左方一格與上方一格的方法數即可得知 P 的方法數，因此其實我們只需要一個一維陣列來紀錄當前 row 的方法數即可。

Time Complexity: O(m x n) time, O(n) space

完整程式碼:

解法一(數學解):

class Solution {

public:

    int uniquePaths(int m, int n) {

        int down = min(m - 1, n - 1); 

        int right = max(m - 1, n - 1); 

        int factorial = down + right;

        long int ans = 1;

        for (int i = factorial; i > right; i--) {

            ans *= i;

        }   

        for (int i = down; i > 0; i--) {

            ans /= i;

        }   

            

        return ans;

    }   

};

解法二( DP ):

class Solution {

public:

    int uniquePaths(int m, int n) {

        vector<int> cur(n,1);

        for (int i = 1; i < m; i++) {

            for (int j = 1; j < n; j++) {

                // cur[j] in right side is previous rows value

                cur[j] = cur[j] + cur[j-1];

            }

        }

        return cur[n-1];

    }

};