這篇文章主要介紹“Java動態(tài)規(guī)劃與組合數(shù)實例分析”的相關(guān)知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“Java動態(tài)規(guī)劃與組合數(shù)實例分析”文章能幫助大家解決問題。

創(chuàng)新互聯(lián)公司致力于網(wǎng)站設(shè)計、成都做網(wǎng)站,成都網(wǎng)站設(shè)計,集團網(wǎng)站建設(shè)等服務(wù)標準化，推過標準化降低中小企業(yè)的建站的成本，并持續(xù)提升建站的定制化服務(wù)水平進行質(zhì)量交付，讓企業(yè)網(wǎng)站從市場競爭中脫穎而出。 選擇創(chuàng)新互聯(lián)公司，就選擇了安全、穩(wěn)定、美觀的網(wǎng)站建設(shè)服務(wù)！

從題目說起

題目原文是：

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

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

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

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

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

示例 1:

輸入: m = 3, n = 2

輸出: 3

解釋:

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

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

示例 2:

輸入: m = 7, n = 3

輸出: 28

正向思路

我們先按照正常思路來想一下，當你處于起點時，你有兩個選擇，向右或者向下，除非你處于最下面一排或者最右邊一列，那你只有一種選擇（比如處于最下面一排，你只能往右），其他位置，你都有兩種選擇。

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

class Solution {  public int uniquePaths(int m, int n) {    // 特殊情況：起點即終點    if (m == 1 && n == 1) {      return 1;    }    // 當前處于(1,1)，終點為(m,n)    return walk(1, 1, m, n);  }  public int walk(int x, int y, int m, int n){    // 已經(jīng)處于終點    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);    // 從當前(x,y)出發(fā)，走到(m,n)，共有多少種走法    return down + right;  }}

優(yōu)化

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

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

假設(shè)我們從(1,1)的位置出發(fā)，終點是(3,3)，那么到達(2,2)這個中間點的話有幾種走法呢？兩種，先到(1,2)再到(2,2)，或者，先到(2,1)再到(2,2)。

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

這就是前面的選擇對于后面的選擇會有影響，即使后面的選擇相同，但由于前面的選擇不同，從而也被認為是不同的選擇。

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

反向思路

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

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

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

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) {          // 最上面一排的點和最左邊一列的點，只能由(1,1)到達          result[i][j] = 1;        } else {          // 其他的點都可以由左邊的點和上面的點到達          result[i][j] = result[i - 1][j] + result[i][j - 1];        }      }    }    return result[m - 1][n - 1];  }}

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

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

一開始我感覺很像分治法，因為都需要將一個大問題分解為子問題，但分治法最終會將子問題合并，但動態(tài)規(guī)劃卻不用。

優(yōu)化

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

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

答案是肯定的，因為每個點的計算只和左邊與上邊相鄰的點有關(guān)，因此，不需要更加久遠的點。

一維數(shù)組

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

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 {          // 其他的點都可以由左邊的點和上面的點到達          dp[j] += dp[j-1];        }      }    }    return dp[m-1];  }}

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

組合數(shù)

因為我們只有向右或向下兩種選擇，而我們一共要走的路徑其實是(m-n-2)，其中有(m-1)的路徑是向右，(n-1)的路徑是向下，其實可以轉(zhuǎn)變?yōu)椋?/p>

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

那么我們可以寫出代碼：

class Solution {  public int uniquePaths(int m, int n) {    // 用double，因為計算出的數(shù)值會很大    double num = 1, denom = 1;    // 找出更小的數(shù)，這樣可以減少計算次數(shù)和計算出的數(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);  }}

關(guān)于“Java動態(tài)規(guī)劃與組合數(shù)實例分析”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點。

新聞標題：Java動態(tài)規(guī)劃與組合數(shù)實例分析
標題鏈接：http://jinyejixie.com/article26/jjipjg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供、網(wǎng)站制作、服務(wù)器托管、定制網(wǎng)站、標簽優(yōu)化、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)