hlg1216数的划分【地推公式|dfs】

好久没刷题了

寒假看了点新的算法

今天确实有点手生了

先看看这个题

Description

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

Input

有多则测试数据。
对于每组测试数据，仅有一行，包括两个整数n，k (6<n<=200，2<=k<=6)。

这个题刚开始做的时候我就觉得是组合数学

然后回想高中赵艳忠怎么跟我们讲的组合数那一部分

最后发现这个题一点不一样

这个题我想出来的两种思路一种是直接dfs190+过得

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = 205;
 7 int n, k;
 8 int ans;
 9 
10 void dfs(int x, int pr, int de) {
11     if(de == k) {
12         ans++;
13         return ;
14     }
15     for(int i = pr; i <= x / 2; i++) {
16         dfs(x - i, i, de + 1);
17     }
18 }
19 
20 int main() {
21     while(EOF != scanf("%d %d",&n, &k) ) {
22         ans = 0;
23         dfs(n, 1, 1);
24         printf("%d
", ans);
25     }
26     return 0;
27 }

View Code

然后我看好多都是0ms过得我就又考虑是不是组合数学

然后看到有说是背包

我就考虑dp

其实这个东西应该一开始就想到的TAT

把一个数n分成k份每一份最少为1

我们这么考虑

首先只要是一个非递减序列就不会重复

然后我们考虑第一位

如果第一位是1

那么就是把n-1个数分成k-1份

如果不是1 那么之后的数肯定大于等于1

我们把每一份都减去1 然后也就是把n-k个数分成k份

f[n,k] = f[n- 1, k - 1] + f[n - k, k]

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int a[205][7];
 7 int f(int n, int k) {
 8     if(n == 0 || k == 0 || n < k) return a[n][k] = 0;
 9     if(n == k) return a[n][k] = 1;
10     if(k == 1) return a[n][k] = 1;
11     if(a[n][k] != -1) return a[n][k];
12     return a[n][k] = f(n - 1, k - 1) + f(n- k, k);
13 }
14 
15 int main() {
16     int n, k;
17     while(EOF != scanf("%d %d",&n, &k) ) {
18         memset(a, -1, sizeof(a));
19         printf("%d
", f(n, k) );
20     }
21     return 0;
22 }
23

View Code