整數(shù)劃分問(wèn)題是算法中的一個(gè)經(jīng)典命題之一庸毫，有關(guān)這個(gè)問(wèn)題的講述在講解到遞歸時(shí)基本都將涉及仔拟。
所謂整數(shù)劃分，是指把一個(gè)正整數(shù)n寫(xiě)成如下形式：
n=m1+m2+…+mi; （其中mi為正整數(shù)岔绸，并且1 <= mi <= n）理逊，則{m1,m2,…,mi}為n的一個(gè)劃分。
如果{m1,m2,…,mi}中的最大值不超過(guò)m盒揉，即max(m1,m2,…,mi)<=m晋被，則稱(chēng)它屬于n的一個(gè)m劃分。這里我們記n的m劃分的個(gè)數(shù)為f(n,m);
例如但n=4時(shí)刚盈，他有5個(gè)劃分羡洛，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};
注意4=1+3 和 4=3+1被認(rèn)為是同一個(gè)劃分。
該問(wèn)題是求出n的所有劃分個(gè)數(shù)，即f(n, n)欲侮。下面我們考慮求f(n,m)的方法;
根據(jù)n和m的關(guān)系崭闲，考慮以下幾種情況：
當(dāng)n=1時(shí)，不論m的值為多少（m>0)威蕉，只有一種劃分即{1};
當(dāng)m=1時(shí)刁俭，不論n的值為多少，只有一種劃分即n個(gè)1韧涨，{1,1,1,…,1};
當(dāng)n=m時(shí)牍戚，根據(jù)劃分中是否包含n，可以分為兩種情況：
(1) 劃分中包含n的情況虑粥，只有一個(gè)即{n}如孝；
(2) 劃分中不包含n的情況，這時(shí)劃分中最大的數(shù)字也一定比n小娩贷，即n的所有(n-1)劃分第晰。
因此 f(n,n) =1 + f(n,n-1);當(dāng)n<m時(shí)，由于劃分中不可能出現(xiàn)負(fù)數(shù)彬祖，因此就相當(dāng)于f(n,n);
但n>m時(shí)茁瘦，根據(jù)劃分中是否包含最大值m，可以分為兩種情況：
(1) 劃分中包含m的情況涧至，即{m, {x1,x2,…xi}}, 其中{x1,x2,… xi} 的和為n-m腹躁，可能再次出現(xiàn)m，因此是（n-m）的m劃分南蓬，因此這種劃分
個(gè)數(shù)為f(n-m, m);
(2) 劃分中不包含m的情況纺非，則劃分中所有值都比m小，即n的(m-1)劃分赘方，個(gè)數(shù)為f(n,m-1);
因此 f(n, m) = f(n-m, m)+f(n,m-1);
綜合以上情況烧颖，我們可以看出，上面的結(jié)論具有遞歸定義特征窄陡，其中（1）和（2）屬于回歸條件炕淮，（3）和（4）屬于特殊情況，將會(huì)轉(zhuǎn)換為情況（5）跳夭。而情況（5）為通用情況涂圆，屬于遞推的方法，其本質(zhì)主要是通過(guò)減小m以達(dá)到回歸條件币叹，從而解決問(wèn)題润歉。其遞推表達(dá)式如下：
f(n, m)= 1; (n=1 or m=1)
f(n, n); (n<m)
1+ f(n, m-1); (n=m)
f(n-m,m)+f(n,m-1); (n>m)
遞歸代碼
import java.util.Scanner;
/**
* Created by EthanWalker on 2017/11/19.
*/
public class IntPartition {
public static int digui(int n, int m) {
if(n==0||m==0) return 0;
if (n == 1 || m == 1) return 1;
if (n == m) return 1 + digui(n, n - 1);
if (n < m) return digui(n, n);
// n>m 時(shí)
return digui(n - m, m) + digui(n, m - 1);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (true) {
int i = scanner.nextInt();
if (i == -1) {
break;
}
long begin = System.currentTimeMillis();
int digui = digui(i, i); //遞歸超時(shí)
long end = System.currentTimeMillis();
System.out.println("遞歸的結(jié)果： " + digui);
System.out.println("花費(fèi)的時(shí)間: "+(end-begin)+" 毫秒");
}
}
}
非遞歸(二維數(shù)組)
import java.util.Scanner;
/**
* Created by EthanWalker on 2017/11/19.
*/
public class IntPartitionArray {
public static int array(int n) {
int[][] a = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
a[i][j] = 0;
}
}
for (int i = 1; i <= n; i++) {
a[i][1] = 1;
a[1][i] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (j == 1 || i == 1) a[i][j] = 1;
else if (i == j) {
a[i][j] = 1 + a[i][i - 1];
} else if (i < j) {
a[i][j] = a[i][i];
} else if (i > j) {
a[i][j] = a[i - j][j] + a[i][j - 1];
}
}
}
return a[n][n];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] a = new int[121][121];
for (int i = 0; i <= 120; i++) {
for (int j = 0; j <= 120; j++) {
a[i][j] = 0;
}
}
for (int i = 1; i <= 120; i++) {
a[i][1] = 1;
a[1][i] = 1;
}
for (int i = 1; i <= 120; i++) {
for (int j = 1; j <= 120; j++) {
if (j == 1 || i == 1) a[i][j] = 1;
else if (i == j) {
a[i][j] = 1 + a[i][i - 1];
} else if (i < j) {
a[i][j] = a[i][i];
} else if (i > j) {
a[i][j] = a[i - j][j] + a[i][j - 1];
}
}
}
while (scanner.hasNext()) {
int i = scanner.nextInt();
// long begin = System.currentTimeMillis();
int array =a[i][i];
// long end = System.currentTimeMillis();
System.out.println(array);
// System.out.println("數(shù)組計(jì)算的結(jié)果: " + array);
// System.out.println("花費(fèi)的時(shí)間: " + (end - begin) + " 毫秒");
}
}
}
