每日算法题（Day6）----分数字

题目描述

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

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

1，1，5； 1，5，1； 5，1，1。

问有多少种不同的分法。

输入格式

输入仅一行，两个整数N 和 K

输出格式

输出仅一行，一个整数即分法。

分析

经典的dp问题，高中数学水平就可以手算，翻译成代码即可

样例

7 3
------------------------
4

代码

#include <cstdio>
#include <iostream>using namespace std;int n,k,dp[10][205];int main()
{
    scanf("%d %d",&n,&k);dp[0][0]=1;for(int i=1;i<=k;i++){
    for(int j=i;j<=n;j++){
    dp[i][j]=dp[i][j-i]+dp[i-1][j-1];}}printf("%d\n",dp[k][n]);return 0;
}