最近在刷力扣上的題目，刷到了65不同路徑，當(dāng)初上大學(xué)的時(shí)候，曾在hihocoder上刷到過(guò)這道題目，但是現(xiàn)在已經(jīng)幾乎全忘光了，大概的知識(shí)點(diǎn)是動(dòng)態(tài)規(guī)劃，如今就讓我們一起來(lái)回顧一下。

從題目說(shuō)起

題目原文是：

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

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

問(wèn)總共有多少條不同的路徑？

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

說(shuō)明：m 和 n 的值均不超過(guò) 100。

示例 1:

輸入: m = 3, n = 2

輸出: 3

解釋:

從左上角開(kāi)始，總共有 3 條路徑可以到達(dá)右下角。

向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右

示例 2:

輸入: m = 7, n = 3

輸出: 28

正向思路

我們先按照正常思路來(lái)想一下，當(dāng)你處于起點(diǎn)時(shí)，你有兩個(gè)選擇，向右或者向下，除非你處于最下面一排或者最右邊一列，那你只有一種選擇（比如處于最下面一排，你只能往右），其他位置，你都有兩種選擇。

因此，我們就根據(jù)這個(gè)思路，可以寫(xiě)出代碼：

class Solution {
  public int uniquePaths(int m, int n) {
    // 特殊情況：起點(diǎn)即終點(diǎn)
    if (m == 1 && n == 1) {
      return 1;
    }
    // 當(dāng)前處于(1,1)，終點(diǎn)為(m,n)
    return walk(1, 1, m, n);
  }
  public int walk(int x, int y, int m, int n){
    // 已經(jīng)處于終點(diǎn)
    if (x >= m && y >= n) {
      return 0;
    }
    // 處于最下面一排或者最右邊一列
    if (x >= m || y >= n) {
      return 1;
    }
    // 往下走，有多少種走法
    int down = walk(x, y + 1, m, n);
    // 往右走，有多少種走法
    int right = walk(x + 1, y, m, n);
    // 從當(dāng)前(x,y)出發(fā)，走到(m,n)，共有多少種走法
    return down + right;
  }
}

優(yōu)化

我們考慮一下，這種寫(xiě)法，有沒(méi)有可以優(yōu)化的地方。

你們應(yīng)該一眼就發(fā)現(xiàn)，walk方法的第一個(gè)判斷if (x >= m && y >= n)，永遠(yuǎn)都不可能為true，因?yàn)橄乱粋€(gè)判斷if (x >= m || y >= n)就已經(jīng)是臨界點(diǎn)情況，直接就已經(jīng)有返回值，根本不可能達(dá)到x >= m && y >= n的情況。因此，該判斷可以刪除。

假設(shè)我們從(1,1)的位置出發(fā)，終點(diǎn)是(3,3)，那么到達(dá)(2,2)這個(gè)中間點(diǎn)的話有幾種走法呢？?jī)煞N，先到(1,2)再到(2,2)，或者，先到(2,1)再到(2,2)。

因此，如果根據(jù)我們上面的寫(xiě)法，從(2,2)到終點(diǎn)(3,3)，我們會(huì)算兩次，雖然這樣的思路本身是正確，但這樣的情況應(yīng)該是可以優(yōu)化的。因?yàn)閺?1,1)到(3,3)，一共只有6種路徑，但已經(jīng)有2條是重復(fù)的路徑了，那么隨著m與n越來(lái)越大，中間點(diǎn)會(huì)越來(lái)越多，那么重復(fù)的路徑也會(huì)越來(lái)越多。

這就是前面的選擇對(duì)于后面的選擇會(huì)有影響，即使后面的選擇相同，但由于前面的選擇不同，從而也被認(rèn)為是不同的選擇。

很明顯，后面的選擇更加唯一，如果我們先在后面做出選擇，那么就可以減少重復(fù)計(jì)算的次數(shù)。因此，我們可以試試反向思路。

反向思路

如果我們不是從起點(diǎn)出發(fā)，而是從終點(diǎn)倒退到起點(diǎn)開(kāi)始算的話。假設(shè)終點(diǎn)是(3,3)，它只能由(2,3)和(3,2)直接到達(dá)，(2,3)也只能由(2,2)和(1,3)直接到達(dá)，(1,3)只能由(1,2)直接到達(dá)，(1,2)只能由(1,1)直接到達(dá)，因此(1,3)只能由(1,1)直達(dá)。

我們可以得出規(guī)律：除了最左邊一列和最上面一排的點(diǎn)，只能由起點(diǎn)(1,1)直達(dá)以外，其他的點(diǎn)(x,y)都是由(x-1,y)和(x,y-1)兩個(gè)點(diǎn)直接到達(dá)的。

因此，根據(jù)這個(gè)思路，我們可以寫(xiě)出代碼：

class Solution {
  public int uniquePaths(int m, int n) {
    int[][] result = new int[m][n];
    int j;
    for (int i = 0; i < m; i++) {
      for (j = 0; j < n; j++) {
        if (i == 0 || j == 0) {
          // 最上面一排的點(diǎn)和最左邊一列的點(diǎn)，只能由(1,1)到達(dá)
          result[i][j] = 1;
        } else {
          // 其他的點(diǎn)都可以由左邊的點(diǎn)和上面的點(diǎn)到達(dá)
          result[i][j] = result[i - 1][j] + result[i][j - 1];
        }
      }
    }
    return result[m - 1][n - 1];
  }
}

其實(shí)這樣的想法就已經(jīng)是動(dòng)態(tài)規(guī)劃的范疇了，我們看看維基上的定義

動(dòng)態(tài)規(guī)劃（英語(yǔ)：Dynamic programming，簡(jiǎn)稱DP）是一種在數(shù)學(xué)、管理科學(xué)、計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)學(xué)和生物信息學(xué)中使用的，通過(guò)把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式求解復(fù)雜問(wèn)題的方法。

一開(kāi)始我感覺(jué)很像分治法，因?yàn)槎夹枰獙⒁粋€(gè)大問(wèn)題分解為子問(wèn)題，但分治法最終會(huì)將子問(wèn)題合并，但動(dòng)態(tài)規(guī)劃卻不用。

優(yōu)化

我們考慮一下，這種寫(xiě)法，有沒(méi)有可以優(yōu)化的地方。

首先是空間上的優(yōu)化，我們一定要用二維數(shù)組嗎？可以用一維數(shù)組代替嗎？

答案是肯定的，因?yàn)槊總€(gè)點(diǎn)的計(jì)算只和左邊與上邊相鄰的點(diǎn)有關(guān)，因此，不需要更加久遠(yuǎn)的點(diǎn)。

一維數(shù)組

假如只用一維數(shù)組，那么只需要存儲(chǔ)上一排的結(jié)果，如果計(jì)算到下一排的時(shí)候，則依次替換，代碼為：

class Solution {
  public int uniquePaths(int m, int n) {
    int[] dp = new int[m];
    int j;
    for(int i = 0; i < n; i++) {
      for(j = 0; j < m; j++) {
        if(j == 0) {
          dp[j] = 1;
        }
        else {
          // 其他的點(diǎn)都可以由左邊的點(diǎn)和上面的點(diǎn)到達(dá)
          dp[j] += dp[j-1];
        }
      }
    }
    return dp[m-1];
  }
}

這樣的優(yōu)化，差不多就結(jié)束了。那我們是否可以從思路上進(jìn)行優(yōu)化呢？

組合數(shù)

因?yàn)槲覀冎挥邢蛴一蛳蛳聝煞N選擇，而我們一共要走的路徑其實(shí)是(m-n-2)，其中有(m-1)的路徑是向右，(n-1)的路徑是向下，其實(shí)可以轉(zhuǎn)變?yōu)椋?/p>

從(m-n-2)中挑出(m-1)，即組合數(shù)C((m-n-2), (m-1))的值

那么我們可以寫(xiě)出代碼：

class Solution {
  public int uniquePaths(int m, int n) {
    // 用double，因?yàn)橛?jì)算出的數(shù)值會(huì)很大
    double num = 1, denom = 1;
    // 找出更小的數(shù)，這樣可以減少計(jì)算次數(shù)和計(jì)算出的數(shù)值
    int small = m > n ? n : m;
    for (int i = 1; i <= small - 1; ++i) {
      num *= m + n - 1 - i;
      denom *= i;
     }
     return (int)(num / denom);
  }
}

總結(jié)

以上所述是小編給大家介紹的Java面試之動(dòng)態(tài)規(guī)劃與組合數(shù),希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
如果你覺(jué)得本文對(duì)你有幫助，歡迎轉(zhuǎn)載，煩請(qǐng)注明出處，謝謝！

最新評(píng)論