求助大神们一个C语言程序实现问题

切·诺万夫斯基

如果想要实现一个正整数n划分成k个不同的数的和，然后求一共有多少种分法，该如何实现？
比如求6划分成3个不同数的和：6=1+2+3，共一种。

845xyz

分解问题 假设三个数分别为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

widsnoy

不知道题主的数据范围，写了一个很裸的暴力。
（其实是太菜了不知道dp该怎么转移，如果有人会的话请务必告诉我）

[C++] 纯文本查看 复制代码

#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);
}