整數(shù)劃分問題是算法中的一個經(jīng)典命題之一，有關(guān)這個問題的講述在講解到遞歸時基本都將涉及。
所謂整數(shù)劃分，是指把一個正整數(shù)n寫成如下形式：
n=m1+m2+…+mi; （其中mi為正整數(shù)，并且1 <= mi <= n），則{m1,m2,…,mi}為n的一個劃分。
如果{m1,m2,…,mi}中的最大值不超過m，即max(m1,m2,…,mi)<=m，則稱它屬于n的一個m劃分。這里我們記n的m劃分的個數(shù)為f(n,m);
例如但n=4時，他有5個劃分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};
注意4=1+3 和 4=3+1被認(rèn)為是同一個劃分。
該問題是求出n的所有劃分個數(shù)，即f(n, n)。下面我們考慮求f(n,m)的方法;

根據(jù)n和m的關(guān)系，考慮以下幾種情況：

1. 當(dāng)n=1時，不論m的值為多少（m>0)，只有一種劃分即{1};

2. 當(dāng)m=1時，不論n的值為多少，只有一種劃分即n個1，{1,1,1,…,1};

3. 當(dāng)n=m時，根據(jù)劃分中是否包含n，可以分為兩種情況：
   (1) 劃分中包含n的情況，只有一個即{n}；
   (2) 劃分中不包含n的情況，這時劃分中最大的數(shù)字也一定比n小，即n的所有(n-1)劃分。
   因此 f(n,n) =1 + f(n,n-1);

4. 當(dāng)n<m時，由于劃分中不可能出現(xiàn)負(fù)數(shù)，因此就相當(dāng)于f(n,n);

5. 但n>m時，根據(jù)劃分中是否包含最大值m，可以分為兩種情況：
   (1) 劃分中包含m的情況，即{m, {x1,x2,…xi}}, 其中{x1,x2,… xi} 的和為n-m，可能再次出現(xiàn)m，因此是（n-m）的m劃分，因此這種劃分
   個數(shù)為f(n-m, m);
   (2) 劃分中不包含m的情況，則劃分中所有值都比m小，即n的(m-1)劃分，個數(shù)為f(n,m-1);
   因此 f(n, m) = f(n-m, m)+f(n,m-1);

綜合以上情況，我們可以看出，上面的結(jié)論具有遞歸定義特征，其中（1）和（2）屬于回歸條件，（3）和（4）屬于特殊情況，將會轉(zhuǎn)換為情況（5）。而情況（5）為通用情況，屬于遞推的方法，其本質(zhì)主要是通過減小m以達(dá)到回歸條件，從而解決問題。其遞推表達(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 時
        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);   //遞歸超時
            long end = System.currentTimeMillis();

            System.out.println("遞歸的結(jié)果： " + digui);
            System.out.println("花費(fèi)的時間: "+(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ù)組計算的結(jié)果: " + array);
//            System.out.println("花費(fèi)的時間: " + (end - begin) + " 毫秒");
        }
    }
}