摘要：作者碼蹄疾畢業(yè)于哈爾濱工業(yè)大學(xué)。機(jī)器人試圖達(dá)到網(wǎng)格的右下角在下圖中標(biāo)記為。問總共有多少條不同的路徑例如，上圖是一個(gè)的網(wǎng)格。有多少可能的路徑說明和的值均不超過。示例輸入輸出解釋從左上角開始，總共有條路徑可以到達(dá)右下角。

作者: 碼蹄疾
畢業(yè)于哈爾濱工業(yè)大學(xué)。 小米廣告第三代廣告引擎的設(shè)計(jì)者、開發(fā)者；
負(fù)責(zé)小米應(yīng)用商店、日歷、開屏廣告業(yè)務(wù)線研發(fā)；
主導(dǎo)小米廣告引擎多個(gè)模塊重構(gòu)；
關(guān)注推薦、搜索、廣告領(lǐng)域相關(guān)知識(shí);

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

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

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

例如，上圖是一個(gè)7 x 3 的網(wǎng)格。有多少可能的路徑？

說明：m 和 n 的值均不超過 100。

示例 1:

輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始，總共有 3 條路徑可以到達(dá)右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

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

這道題拿到題目我覺得大家的第一反應(yīng)都是這應(yīng)該是遞歸的題目,因?yàn)槲覀兛梢赞D(zhuǎn)化為子問題，但是這樣暴力肯定會(huì)超時(shí),就不用嘗試了。其實(shí)在該題遞歸的方法就是從上面到下面不斷的去嘗試,如果我們能記住之前的結(jié)果,就對(duì)我們下一步有幫助,所以想到了DP的方法。
格子中的數(shù)字代表當(dāng)前的方法.

初始狀態(tài)

當(dāng)前這個(gè)狀態(tài)只和左邊和上邊的格子有關(guān)系.

依次求解

于是我們可以得到狀態(tài)轉(zhuǎn)移方程：

ways[i][j] = ways[i-1][j] + ways[i][j-1];

public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] ways = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) ways[i][j] = 1;
                else ways[i][j] = ways[i-1][j] + ways[i][j-1];
            }
        }
        return ways[m-1][n-1];
    }
}

上面圖3我們?cè)谇蠼獾臅r(shí)候,我們是一行一行求解的,實(shí)際上我們只需要記錄遍歷到(i, j)這個(gè)位置的時(shí)候當(dāng)前行有幾種路徑,如果遍歷到(i, m-1)的時(shí)候,替換掉這一行對(duì)應(yīng)列的路徑即可，于是狀態(tài)轉(zhuǎn)移方程編程:
res[j] = res[j] + res[j-1]

class Solution {
    public int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        int[] res = new int[n];
        res[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                res[j] += res[j - 1];
                System.out.println("i=" + i + "_" + "j=" + j + ":" + Arrays.toString(res));
            }
        }
        return res[n - 1];
    }
}

有的同學(xué)可能還是不理解,我在代碼里面打印了一些信息方便理解：

i=0_j=1:[1, 1, 0, 0, 0, 0, 0]
i=0_j=2:[1, 1, 1, 0, 0, 0, 0]
i=0_j=3:[1, 1, 1, 1, 0, 0, 0]
i=0_j=4:[1, 1, 1, 1, 1, 0, 0]
i=0_j=5:[1, 1, 1, 1, 1, 1, 0]
i=0_j=6:[1, 1, 1, 1, 1, 1, 1] //只記錄到這一行的信息
i=1_j=1:[1, 2, 1, 1, 1, 1, 1]
i=1_j=2:[1, 2, 3, 1, 1, 1, 1]
i=1_j=3:[1, 2, 3, 4, 1, 1, 1]
i=1_j=4:[1, 2, 3, 4, 5, 1, 1]
i=1_j=5:[1, 2, 3, 4, 5, 6, 1]
i=1_j=6:[1, 2, 3, 4, 5, 6, 7] //只記錄到這一行的信息
i=2_j=1:[1, 3, 3, 4, 5, 6, 7]
i=2_j=2:[1, 3, 6, 4, 5, 6, 7]
i=2_j=3:[1, 3, 6, 10, 5, 6, 7]
i=2_j=4:[1, 3, 6, 10, 15, 6, 7]
i=2_j=5:[1, 3, 6, 10, 15, 21, 7]
i=2_j=6:[1, 3, 6, 10, 15, 21, 28] //只記錄到這一行的信息
i=3_j=1:[1, 4, 6, 10, 15, 21, 28]
i=3_j=2:[1, 4, 10, 10, 15, 21, 28]
i=3_j=3:[1, 4, 10, 20, 15, 21, 28]
i=3_j=4:[1, 4, 10, 20, 35, 21, 28]
i=3_j=5:[1, 4, 10, 20, 35, 56, 28]
i=3_j=6:[1, 4, 10, 20, 35, 56, 84] //只記錄到這一行的信息

這個(gè)題其實(shí)可以用排列組合的方式來做。這其實(shí)是最開始想到的方法。
以模擬的[4, 7]的例子,每一條路徑：

向右的肯定有6步;

向左的肯定有3步;

問題即為:c(9,3) = (9 8 7) / (1 2 3) = 84

組合數(shù)公式：c(m,n) = m! / (n! * (m - n)!)

java直接套用公式會(huì)越界,下面結(jié)果我用long存儲(chǔ):

1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
11!=39916800
12!=479001600
13!=6227020800
14!=87178291200
15!=1307674368000
16!=20922789888000
17!=355687428096000
18!=6402373705728000
19!=121645100408832000
20!=2432902008176640000
21!=-4249290049419214848
22!=-1250660718674968576
23!=8128291617894825984
24!=-7835185981329244160

需要稍微化簡一下,化簡的過程就是我求解c(9,3)的第二步驟。

class Solution {
    public int uniquePaths(int m, int n) {
        double dom = 1;
        double dedom = 1;
        int small = m < n ? m - 1 : n - 1;
        int big = m < n ? n - 1 : m - 1;
        for (int i = 1; i <= small; i++) {
            dedom *= i;
            dom *= small + big + 1 - i;
        }
        return (int) (dom / dedom);
    }
}

python代碼就比較兇殘了,一行代碼搞定:

class Solution:
    def uniquePaths(self, m, n):
        return int(math.factorial(m + n - 2) / math.factorial(m -1) / math.factorial(n-1))

貼一下DP版本的代碼

class Solution:
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m <= 0 or n <= 0:
            return 0
        res = [0 for _ in range(0, n)]
        res[0] = 1
        for i in range(0, m):
            for j in range(1, n):
                res[j] += res[j-1]
        return res[n-1]

【Leetcode】61.旋轉(zhuǎn)鏈表

【Leetcode】60. 第k個(gè)排列