求助大神们一个C语言程序实现问题
如果想要实现一个正整数n划分成k个不同的数的和，然后求一共有多少种分法，该如何实现？比如求6划分成3个不同数的和：6=1+2+3，共一种。 分解问题 假设三个数分别为a b c
条件1：且(a.max)/2>=(b.max) & (b.max/2>=c.max) 用于明确循环边界
条件2：a最大可为n-3 即b=2 c=1
条件3：a!=b & b!=c 不知道题主的数据范围，写了一个很裸的暴力。
（其实是太菜了不知道dp该怎么转移，如果有人会的话请务必告诉我）
#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, k, ans;
void dfs(int x, int sum, int kk) {
if(kk > k) return;
if(sum == n && kk == k) {
ans++;
return;
}
for(int i = x + 1; sum + i <= n; i++) {
dfs(i, sum + i, kk + 1);
}
}
int main() {
scanf("%d %d", &n, &k);
dfs(0, 0, 0);
printf("%d\n",ans);
}
页:
[1]