力扣 --- 不同路徑（動态規劃）

題目

一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中标記為 “Start” ）。

機器人每次隻能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中标記為 “Finish” ）。

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

示例 1：

輸入：m = 3, n = 7

輸出：28

示例 2：

輸入：m = 3, n = 2

輸出：3

解釋：

從左上角開始，總共有 3 條路徑可以到達右下角。

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

輸入：m = 7, n = 3

輸出：28

示例 4：

輸入：m = 3, n = 3

輸出：6

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/unique-paths

方法一

本題也是動态規劃的經典問題，對于這個二維數組的地圖，我們可以看成，對于每個位置的路徑數f(i,j)一定等于f(i-1,j)和f(i,j-1)的路徑數的總和。

由此我們可以得出動态規劃的方程：fn(i,j) = f(i-1,j) + f(i,j-1).

而對于i=0或者j=0的位置，它的路徑數均為1

var uniquePaths = function(m, n) {
	//二維數組用來标記每個位置的路徑數
    let arr = new Array(m);
    for(var i=0;i<arr.length;i++){
        arr[i] = new Array(n).fill(0)
    }
    //給邊緣條件的置為1
    for(var i=0;i<m;i++){
        arr[i][0] = 1;
    }
    for(var i=0;i<n;i++){
        arr[0][i] = 1;
    }
	//通過動态規劃的狀态方程來進行求解
    for(var i=1;i<m;i++){
        for(var j=1;j<n;j++){
            arr[i][j] = arr[i-1][j] + arr[i][j -1]
        }
    }
    return arr[m-1][n-1]

};
           

方法二

這道題我們可以把它歸納為一個數學問題，對于一個長度為m，寬度為n的為數組。

我們從左上角到右下角的距離為（m + n - 2）。

也就是要走m + n - 2 步。

但是在這裡面我們要向下走m - 1 步。

是以這道題的思路就可以演變成我們從m + n - 2 中有多少種 m - 1 的方案。

也就是，答案的結果應該為C(m+n-2 , n-1)

var uniquePaths = function(m, n) {
    let ans = 1;
    for (let x = n, y = 1; y < m; ++x, ++y) {
        ans = Math.floor(ans * x / y);
    }
    return ans;
};