NOIP2001提高组 数的划分_算法提高 数的划分

NOIP2001提高组 数的划分

题目描述

    将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。
    例如：n=7，k=3，下面三种分法被认为是相同的。
    1，1，5; 1，5，1; 5，1，1;
    问有多少种不同的分法。

输入输出格式

    输入格式：

    n，k (6<n<=200，2<=k<=6)

    输出格式：

    一个整数，即不同的分法。

输入输出样例

    输入样例：

    7 3

    输出样例：

    4

解题分析：

    方法一

    动态规划
    状态：f(i, j)表示将数i分成j份。
    状态转移方程：f(i, j) = f(i-1, j-1)+f(i-j, j)。划分方案中有1的方案数为f(i-1, j-1)，即假设第一个是1，然后将剩下的i-1划分为j-1份（有1或没有1都算）；划分方案中没有1的方案数为f(i-j, j)，即先将每份中放置一个1，然后将剩下的i-j再划分为j份（i-j>=j）。
    初始条件：f(i, i) = 1, f(i, 1) = 1。
    程序比较简单，这里就不贴出。

    方法二

    DFS
    对每一个i出现的次数进行枚举，对于每一种情形判断是否满足条件，如果满足，则结果加1。
    但是，如果不进行剪枝，则肯定会超时。
    除了边界判断等一般剪枝外，还可以进行下列两个剪枝：
    1、如果已经分为k-1份，则不需要继续搜索，只要判断所差的数（n-a，a是已经得到的和）是否大于下一个要搜索的数m，如果大于，则结果加1。

    2、假设已经得到了k1份，如果n-a小于(k-k1)*m(m为下一个要搜索的数)，则不需要继续搜索下去。（强剪枝）