简单的整数划分问题

总时间限制: 100ms 内存限制: 65536kB 描述 将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。 正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。

输入 标准的输入包含若干组测试数据。每组测试数据是一个整数N(0 < N <= 50)。 输出 对于每组测试数据，输出N的划分数。 样例输入 5 样例输出 7 提示 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

解题思路： 该问题是求出n的所有划分个数，即f(n, n)。下面我们考虑求f(n,k)的方法; 根据n和k的关系，考虑以下几种情况： （1）当 n = 1 时，不论k的值为多少（k > 0 )，只有一种划分即 { 1 }; ( 2 ) 当 k = 1 时，不论n的值为多少，只有一种划分即 n 个 1，{ 1, 1, 1, …, 1 }; (3) 当 n = k 时，根据划分中是否包含 n，可以分为两种情况： (a). 划分中包含n的情况，只有一个即 { n }； (b). 划分中不包含n的情况，这时划分中最大的数字也一定比 n 小，即 n 的所有 ( n - 1 ) 划分。 因此 f(n, n) = 1 + f(n, n-1); (4) 当 n < k 时，由于划分中不可能出现负数，因此就相当于 f(n, n); (5) 但 n > k 时，根据划分中是否包含最大值 k，可以分为两种情况： (a). 划分中包含 k 的情况，即 { k, { x1, x2, …, xi } }, 其中 { x1, x2, …, xi } 的和为 n - k，可能再次出现 k，因此是（n - k）的 k 划分，因此这种划分 个数为 f(n-k, k); (b). 划分中不包含 k 的情况，则划分中所有值都比 k 小，即 n 的 ( k - 1 ) 划分，个数为 f(n, k - 1); 因此 f(n, k) = f(n - k, k) + f(n, k - 1);

Java代码如下：

import java.util.Scanner;

public class Main {

    public static int Function(int n,int k){
        if (n == 1 || k == 1){
            return 1;
        }
        if (n < k){
            return Function(n, n);
        }
        if ( n == k){
            return Function(n, k-1)+1;
        }
        return Function(n-k, k)+Function(n, k-1);
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(Function(n, n));

        in.close();
    }

}