題目描述（中等難度）

機(jī)器人從左上角走到右下角，只能向右或者向下走。輸出總共有多少種走法。

解法一 遞歸

求 ( 0 , 0 ) 點(diǎn)到（ m - 1 , n - 1） 點(diǎn)的走法。

（0，0）點(diǎn)到（m - 1 , n - 1） 點(diǎn)的走法等于（0，0）點(diǎn)右邊的點(diǎn) （1，0）到（m - 1 , n - 1）的走法加上（0，0）點(diǎn)下邊的點(diǎn)（0，1）到（m - 1 , n - 1）的走法。

而左邊的點(diǎn)（1，0）點(diǎn)到（m - 1 , n - 1） 點(diǎn)的走法等于（2，0） 點(diǎn)到（m - 1 , n - 1）的走法加上（1，1）點(diǎn)到（m - 1 , n - 1）的走法。

下邊的點(diǎn)（0，1）點(diǎn)到（m - 1 , n - 1） 點(diǎn)的走法等于（1，1）點(diǎn)到（m - 1 , n - 1）的走法加上（0，2）點(diǎn)到（m - 1 , n - 1）的走法。

然后一直遞歸下去，直到 （m - 1 , n - 1） 點(diǎn)到（m - 1 , n - 1） ，返回 1。

public int uniquePaths(int m, int n) {
    HashMap<String, Integer> visited = new HashMap<>();
    return getAns(0, 0, m - 1, n - 1, 0);

}

private int getAns(int x, int y, int m, int n, int num) {
    if (x == m && y == n) {
        return 1;
    }
    int n1 = 0;
    int n2 = 0;
    //向右探索的所有解
    if (x + 1 <= m) {
        n1 = getAns(x + 1, y, m, n, num);
    }
    //向左探索的所有解
    if (y + 1 <= n) {
        n2 = getAns(x, y + 1, m, n, num);
    }
    //加起來(lái)
    return n1 + n2;
}

時(shí)間復(fù)雜度：

空間復(fù)雜度：

遺憾的是，這個(gè)算法在 LeetCode 上超時(shí)了。我們可以優(yōu)化下，問(wèn)題出在當(dāng)我們求點(diǎn) （x，y）到（m - 1 , n - 1） 點(diǎn)的走法的時(shí)候，遞歸求了點(diǎn) （x，y）點(diǎn)右邊的點(diǎn) （x + 1，0）到（m - 1 , n - 1）的走法和（x，y）下邊的點(diǎn)（x，y + 1）到（m - 1 , n - 1）的走法。而沒(méi)有考慮到（x + 1，0）到（m - 1 , n - 1）的走法和點(diǎn)（x，y + 1）到（m - 1 , n - 1）的走法是否是之前已經(jīng)求過(guò)了。事實(shí)上，很多點(diǎn)求的時(shí)候后邊的的點(diǎn)已經(jīng)求過(guò)了，所以再進(jìn)行遞歸是沒(méi)有必要的?；诖?，我們可以用 visited 保存已經(jīng)求過(guò)的點(diǎn)。

public int uniquePaths(int m, int n) {
    HashMap<String, Integer> visited = new HashMap<>();
    return getAns(0, 0, m - 1, n - 1, 0, visited); 

}
private int getAns(int x, int y, int m, int n, int num, HashMap<String, Integer> visited) {
    if (x == m && y == n) {
        return 1;
    }
    int n1 = 0;
    int n2 = 0;
    String key = x + 1 + "@" + y;
    //判斷當(dāng)前點(diǎn)是否已經(jīng)求過(guò)了
    if (!visited.containsKey(key)) {
        if (x + 1 <= m) {
            n1 = getAns(x + 1, y, m, n, num, visited);
        }
    } else {
        n1 = visited.get(key);
    }
    key = x + "@" + (y + 1);
    if (!visited.containsKey(key)) {
        if (y + 1 <= n) {
            n2 = getAns(x, y + 1, m, n, num, visited);
        }
    } else {
        n2 = visited.get(key);
    }
    //將當(dāng)前點(diǎn)加入 visited 中
    key = x + "@" + y;
    visited.put(key, n1+n2);
    return n1 + n2;
}

時(shí)間復(fù)雜度：

空間復(fù)雜度：

解法二 動(dòng)態(tài)規(guī)劃

解法一是基于遞歸的，壓棧浪費(fèi)了很多時(shí)間。我們來(lái)分析一下，壓棧的過(guò)程，然后我們其實(shí)完全可以省略壓棧的過(guò)程，直接用迭代去實(shí)現(xiàn)。

如下圖，如果是遞歸的話，根據(jù)上邊的代碼，從 （0，0）點(diǎn)向右壓棧，向右壓棧，到最右邊后，就向下壓棧，向下壓棧，到最下邊以后，就開(kāi)始出棧。出棧過(guò)程就是橙色部分。

然后根據(jù)代碼，繼續(xù)壓棧前一列，下圖的橙色部分，然后到最下邊后，然后開(kāi)始出棧，根據(jù)它的右邊的點(diǎn)和下邊的點(diǎn)計(jì)算當(dāng)前的點(diǎn)的走法。

接下來(lái)兩步同理，壓棧，出棧。

我們現(xiàn)在要做的就是要省略壓棧的過(guò)程，直接出棧。很明顯可以做到的，只需要初始化最后一列為 1 ，然后 1 列，1 列的向前更新就可以了。有一些動(dòng)態(tài)規(guī)劃的思想了。

public int uniquePaths(int m, int n) {
    int[] dp = new int[m];
    //初始化最后一列
    for (int i = 0; i < m; i++) {
        dp[i] = 1;
    }
    //從右向左更新所有列
    for (int i = n - 2; i >= 0; i--) {
        //最后一行永遠(yuǎn)是 1，所以從倒數(shù)第 2 行開(kāi)始
        //從下向上更新所有行
        for (int j = m - 2; j >= 0; j--) {
            //右邊的和下邊的更新當(dāng)前元素
            dp[j] = dp[j] + dp[j + 1];
        }
    }
    return dp[0];
}

時(shí)間復(fù)雜度：O（m * n）。

空間復(fù)雜度：O（m）。

這里也有一個(gè)類似的想法。不過(guò)他是正向考慮的，和上邊的想法剛好相反。如果把 dp [ i ] [ j ] 表示為從點(diǎn) （0，0）到點(diǎn) ( i，j）的走法。

上邊解法公式就是 dp [ i ] [ j ] = dp [ i + 1 ] [ j ] + dp [ i ] [ j +1 ]。

這里的話就是 dp [ i ] [ j ] = dp [ i - 1 ] [ j ] + dp [ i ] [ j - 1 ]。就是用它左邊的和上邊的更新，可以結(jié)合下圖。

這樣的話，就是從左向右，從上到下一行一行更新（當(dāng)前也可以一列一列更新）。

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[(n - 1)];
}

時(shí)間復(fù)雜度：O（m * n）。

空間復(fù)雜度：O（n）。

解法三 公式

參考這里。

我們用 R 表示向右，D 表示向下，然后把所有路線寫出來(lái)，就會(huì)發(fā)現(xiàn)神奇的事情了。

R R R D D

R R D D R

R D R D R

……

從左上角，到右下角，總會(huì)是 3 個(gè) R，2 個(gè) D，只是出現(xiàn)的順序不一樣。所以求解法，本質(zhì)上是求了組合數(shù)，N = m + n - 2，也就是總共走的步數(shù)。 k = m - 1，也就是向下的步數(shù)，D 的個(gè)數(shù)。所以總共的解就是 。

public int uniquePaths(int m, int n) {
    int N = n + m - 2; 
    int k = m - 1;  
    long res = 1; 
    for (int i = 1; i <= k; i++)
        res = res * (N - k + i) / i;
    return (int) res; 
}

時(shí)間復(fù)雜度：O（m）。

空間復(fù)雜度：O（1）。

總

從遞歸，到遞歸改迭代，之前的題也都遇到過(guò)了，本質(zhì)上就是省去壓棧的過(guò)程。解法三的公式法，直接到問(wèn)題的本質(zhì)，很厲害。

更多詳細(xì)通俗題解詳見(jiàn) leetcode.wang 。