題目描述：

輸入m,n，分別表示蘋果數與盤子的總數，要求輸出蘋果放在n個盤子的方法總數（注意511和151是一種情況），例如輸入 7 3 輸出8（（7），（6,1），（5,2），（4,3），（5,1,1），（4,2,1），（3,3,1），（3,2,2））

思路：

最典型的解法整數分解，例如給定n個蘋果，把蘋果放到k個盤子里，允許有的盤子為空，不妨設 f（n , k ) (邊緣條件為當 n = 0 ，1時，返回1，當 k = 1 時，返回1）表示結果，分析一下可以知道有兩種放的方法，一種是有空盤，一種是沒空盤。

沒空盤的情況可以知道每個盤子里至少有一個蘋果，也就是說這種情況的總數為 f ( n-k , k ) 。

而有空盤的情況，我們可以假設最后一個盤子為空，則這種情況的總數為f ( n , k-1 ) (無需考慮多個盤子為空的情況，遞歸時必然會出現）

所以狀態轉移方程為 f ( n , k ) = f ( n-k , k ) + f ( n , k-1 )

1 import java.util.Scanner; 2 3 /** 4 * 把M個同樣的蘋果放在N個同樣的盤子里，允許有的盤子空著不放， 5 * 問共有多少種不同的分法？（用K表示）5，1，1和1，5，1 是同一種分法。 6 */ 7 public class PlayApples { 8 9 public static void main(String[] args) { 10 //輸入讀取參數 11 Scanner cin = new Scanner(System.in) ; 12 int apples = cin.nextInt() ; 13 int planes = cin.nextInt() ; 14 cin.close(); 15 16 System.out.println(count(apples,planes)) ; 17 18 } 19 20 /** 21 * 最典型的整數分解 22 * 例如給定n個蘋果，把蘋果放到k個盤子里，允許有的盤子為空， 不妨設 f（m , n ) 23 * (邊緣條件為當 m == 0 ，1時，返回1，當 n == 1 時，返回1）表示結果， 24 * 分析一下可以知道有兩中放的方法，一種是有空盤，一種是沒空盤， 25 * 沒空盤的情況可以知道每個盤子里至少有一個蘋果，也就是說這種情況的總數為 f ( n-k , k ) 。 26 * 而有空盤的情況，我們可以假設最后一個盤子為空，則這種情況的總數為f ( n , k-1 ) (無需考慮多個盤子為空的情況，遞歸時必然會出現） 27 * 所以狀態轉移方程為 f ( n , k ) = f ( n-k , k ) + f ( n , k-1 )。 28 * 29 * 而如果是不允許有空盤子的情況，則可以由上面的情況推出， 30 * 設 d ( n , k ) 表示把n個蘋果放到k個盤子里，不允許有空盤子的方法總數， 31 * 則有f ( n , k ) = Σ ( 1 <= i <= k ) d ( n , i ) 32 * 所以 d ( n , k ) = f ( n , k ) - f ( n , k-1 ) 33 * 34 * @param m 蘋果數量 35 * @param n 盤子數量 36 * @return 37 */ 38 private static int count(int m, int n) { 39 //n為0 是錯誤的，故返回0 40 if(n == 0){ 41 return 0 ; 42 } 43 //m == 0,1時和 n == 1時均只有一種放法 44 if(m == 0 || n == 1 || m == 1 ){ 45 return 1 ; 46 }else if(m < 0){ 47 //m < 0 時，也是錯誤的情形，所以返回0 48 return 0 ; 49 }else{ 50 //遞歸調用 51 return count(m-n,n) + count(m,n-1) ; 52 } 53 } 54 } Code

?

擴展：

而如果是不允許有空盤子的情況，則可以由上面的情況推出，設 d ( n , k ) 表示把n個蘋果放到k個盤子里，不允許有空盤子的方法總數，則有

f ( n , k ) = Σ ( 1 <= i <= k ) d ( n , i ) 所以 d ( n , k ) = f ( n , k ) - f ( n , k-1 )

轉載于:https://www.cnblogs.com/mukekeheart/p/5594225.html

總結

以上是生活随笔為你收集整理的华为OJ平台——放苹果（典型整数划分问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。