您好,登錄后才能下訂單哦!
這篇文章主要介紹“Java動(dòng)態(tài)規(guī)劃與組合數(shù)實(shí)例分析”的相關(guān)知識(shí),小編通過(guò)實(shí)際案例向大家展示操作過(guò)程,操作方法簡(jiǎn)單快捷,實(shí)用性強(qiáng),希望這篇“Java動(dòng)態(tài)規(guī)劃與組合數(shù)實(shí)例分析”文章能幫助大家解決問(wèn)題。
從題目說(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)稱(chēng)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); }}
關(guān)于“Java動(dòng)態(tài)規(guī)劃與組合數(shù)實(shí)例分析”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí),可以關(guān)注億速云行業(yè)資訊頻道,小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。