Luogu P1025 数的划分(递推 DP DFS)

 P1025 数的划分

题目描述

将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1，1，5; 1，5，1; 5，1，1;

问有多少种不同的分法。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

7 3

输出样例#1：

4

说明

四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;

noip2001年提高组第二题

　　这道题对于我来说是一道有难度的题((´-_-)-_-)-_-)

　　有三种思路，递推，DP，爆搜(dfs骗分神器)！

　　AC①:dfs (24ms)

　　

#include <cstdio>

int ans, n, k;

// left表示还有多大数字没分
// num表示还需分成几份
// last表示上次分的数字是多少
void dfs(int left, int num, int last)
{    //条件
    if(num == 1)
    {
        ans++;
        return;
    }
    else
    {    //为什么是i = last  因为要避免分的重复 这样就能从小到大以次分(剪枝)
        //为什么i<=left/num 因为要保证后面的几份也能分到一个数
        for(int i=last; i<= left/num; i++)
            dfs(left-i, num-1, i);
    }
}

int main()
{
    scanf("%d%d", &n, &k);
    //把n分成k份 从1开始分
    dfs(n, k, 1);
    printf("%d", ans);
    return 0;
}

　　第二种方法是递推

　　这里要感谢DoubleCakes大大的 http://blog.csdn.net/u013174702/article/details/45620723

　　把n看成是n个小球，k看成是k个盒子

　　那么题目就变成了把n小球放到k个盒子，且每个盒子都至少有1个小球的问题。

　　那么把n个小球放到k个盒子里的情况总数 = 1.至少有1个盒子放1个小球的情况总数 + 2.每个盒子都有多于1个小球的情况总数

　　那么这里 1 相当于 把n-1个小球放到k-1个盒子里的情况总数

　　2 相当于 把n-k个小球放到k个盒子里的情况总数

　　到了这里就可以发现是递推咯。

　　公式为 f(n,k) = f(n-1,k-1) + f(n-k,k)

　　你说n<k时候？ 请看代码

　　AC②: 递推 (32ms)

#include <cstdio>

int ss(int n, int k)
{
    if(n < k) return 0;    //如果n<k 肯定不可能每个盒子都有
    if(n == k) return 1;//盒子和小球数相等 只有一种方案 每个盒子里一个小球
    if(k == 1) return 1;//盒子只有一个时候 把剩下小球都放进去
    return ss(n-1, k-1) + ss(n-k, k);
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    printf("%d", ss(n, k));
    return 0;
}

　　第三种方法是DP

　　其实理解了递推，那么就能理解dp了。

　　方程为f[i][j] = f[i-1][j-1] + f[i-j][j]

　　边界 f[0][0] = 1

　　那么还有不懂就看代码吧

　　AC⑨: dp(0ms dp大法好)

#include <cstdio>

int f[205][10];
//f[n][k]表示将n分成k份的方案总数
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    f[0][0] = 1;
    for(int i=1; i<=n; i++)
    {
        // j<=i保证i-j>=0   要记得还有 j<=k
        for(int j=1; j<=i && j<=k; j++)
        {
            f[i][j] = f[i-1][j-1] + f[i-j][j];
        }
    }
    printf("%d", f[n][k]);
    return 0;
}