溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“Java組合數的使用方法”，在日常操作中，相信很多人在Java組合數的使用方法問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java組合數的使用方法”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
題目原文是：
>一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為“Start” ）。
>機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為“Finish”）。
>問總共有多少條不同的路徑？
>例如，上圖是一個7 x 3 的網格。有多少可能的路徑？
>說明：m 和 n 的值均不超過 100。
>示例 1:
>>輸入: m = 3, n = 2
>>輸出: 3
>>解釋:
>>從左上角開始，總共有 3 條路徑可以到達右下角。
>>1. 向右 -> 向右 -> 向下
>>2. 向右 -> 向下 -> 向右
>>3. 向下 -> 向右 -> 向右
>示例 2:
>>輸入: m = 7, n = 3
>>輸出: 28
我們先按照正常思路來想一下，當你處于起點時，你有兩個選擇，向右或者向下，除非你處于最下面一排或者最右邊一列，那你只有一種選擇（比如處于最下面一排，你只能往右），其他位置，你都有兩種選擇。
因此，我們就根據這個思路，可以寫出代碼：
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){
// 已經處于終點
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)出發，走到(m,n)，共有多少種走法
return down + right;
}
}我們考慮一下，這種寫法，有沒有可以優化的地方。
你們應該一眼就發現，walk方法的第一個判斷if (x >= m && y >= n)，永遠都不可能為true，因為下一個判斷if (x >= m || y >= n)就已經是臨界點情況，直接就已經有返回值，根本不可能達到x >= m && y >= n的情況。因此，該判斷可以刪除。
假設我們從(1,1)的位置出發，終點是(3,3)，那么到達(2,2)這個中間點的話有幾種走法呢？兩種，先到(1,2)再到(2,2)，或者，先到(2,1)再到(2,2)。
因此，如果根據我們上面的寫法，從(2,2)到終點(3,3)，我們會算兩次，雖然這樣的思路本身是正確，但這樣的情況應該是可以優化的。因為從(1,1)到(3,3)，一共只有6種路徑，但已經有2條是重復的路徑了，那么隨著m與n越來越大，中間點會越來越多，那么重復的路徑也會越來越多。
這就是前面的選擇對于后面的選擇會有影響，即使后面的選擇相同，但由于前面的選擇不同，從而也被認為是不同的選擇。
很明顯，后面的選擇更加唯一，如果我們先在后面做出選擇，那么就可以減少重復計算的次數。因此，我們可以試試反向思路。
如果我們不是從起點出發，而是從終點倒退到起點開始算的話。假設終點是(3,3)，它只能由(2,3)和(3,2)直接到達，(2,3)也只能由(2,2)和(1,3)直接到達，(1,3)只能由(1,2)直接到達，(1,2)只能由(1,1)直接到達，因此(1,3)只能由(1,1)直達。
我們可以得出規律：除了最左邊一列和最上面一排的點，只能由起點(1,1)直達以外，其他的點(x,y)都是由(x-1,y)和(x,y-1)兩個點直接到達的。
因此，根據這個思路，我們可以寫出代碼：
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];
}
}其實這樣的想法就已經是動態規劃的范疇了，我們看看維基上的定義
>動態規劃（英語：Dynamic programming，簡稱DP）是一種在數學、管理科學、計算機科學、經濟學和生物信息學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。
一開始我感覺很像分治法，因為都需要將一個大問題分解為子問題，但分治法最終會將子問題合并，但動態規劃卻不用。
我們考慮一下，這種寫法，有沒有可以優化的地方。
首先是空間上的優化，我們一定要用二維數組嗎？可以用一維數組代替嗎？
答案是肯定的，因為每個點的計算只和左邊與上邊相鄰的點有關，因此，不需要更加久遠的點。
假如只用一維數組，那么只需要存儲上一排的結果，如果計算到下一排的時候，則依次替換，代碼為：
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];
}
}這樣的優化，差不多就結束了。那我們是否可以從思路上進行優化呢？
因為我們只有向右或向下兩種選擇，而我們一共要走的路徑其實是(m-n-2)，其中有(m-1)的路徑是向右，(n-1)的路徑是向下，其實可以轉變為：
>從(m-n-2)中挑出(m-1)，即組合數C((m-n-2), (m-1))的值
那么我們可以寫出代碼：
class Solution {
public int uniquePaths(int m, int n) {
// 用double，因為計算出的數值會很大
double num = 1, denom = 1;
// 找出更小的數，這樣可以減少計算次數和計算出的數值
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);
}
}到此，關于“Java組合數的使用方法”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
