标签归档:dynamic programming

数的划分

问题描述
【描述 Description】
将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。
例如:n=7,k=3,下面三种分法被认为是相同的。
1,1,5; 1,5,1; 5,1,1;

问有多少种不同的分法。

【输入格式 Input Format】
输入n,k (6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
 
int main()
{
 
       int a[201][10] = {0};
       int n, m, i, j;
 
       scanf("%d%d", &n, &m);
       a[0][0] = 1;
 
       for (i = 1; i <= n; i++)
       {
              for (j = 1; j <= m; j++)
                     if (i >= j )
                            a[i][j] = a[i - j][j] + a[i - 1][j - 1];                
       }
 
              printf("%d\n", a[n][m]);
       return 0;
}