首页 > 代码库 > 数的划分(动规)

数的划分(动规)

数的划分

总时间限制: 
1000ms
 
内存限制: 
65536kB
描述

将整数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
提示
四种分法为:1,1,5;1,2,4;1,3,3;2,2,3。
来源
NOIP2001复赛 提高组 第二题
【思路】
和前面放苹果的题很相似,只是放苹果的题目允许有空的而这个不允许有空的;
那你就现在每个盘子里放一个苹果保证以后怎么放都不为空,然后就变成了放苹果的题目‘’;  
【代码】
#include<iostream>
#include<cstdio>
using namespace std;
int n,k;
int dp(int n,int k)
{
    if(k==1||n==0)return 1;
    if(n<k)return dp(n,n);
    else
    return dp(n,k-1)+dp(n-k,k);
    
}
int main()
{

    scanf("%d%d",&n,&k);
    cout<<dp(n-k,k)<<endl;//n-k为先在每个盘子放一个苹果保证不为空,那再放你爱怎么搞怎么搞~
    return 0;
}

 

数的划分(动规)