/*
经典DP了
将整数i分成j份，对1进行讨论
若每份都大于1，即先将i分出j来使每份为1，问题转化为将剩下的i-j分成j份的问题
若至少有一份为1，1已经占了一份，问题转化为将i-1分成j-1份的问题
设f[i][j]表示数i分成j份的划分方案数
可得f[i][j]=f[i-j][j]+f[i-1][j-1]
然后两个顺序递推就好了 初值f[0][0]=1 f[i][1]=1
这个第一个转移有点难理解啊
其实就是我们i分成j份
如果不包含1即每份都大于1   即每个拆出来的数都可以表示为x+1
所以我们相当于每个数加上了一个1上去
这样就完成了一个状态的转移
注意i>=j 因为不可能分的份数比自己还多OTZ
然后就推出来了
然后你就AC了此题
*/
#include <cstdio>
using namespace std;

int f[210][7];
int n,k,i,j;

int main()
{
    scanf("%d%d",&n,&k);
    f[0][0]=1;
    for(i=1;i<=n;i++)
        f[i][1]= 1;
    for(i=1;i<=n;i++)
        for(j=1;j<=k;j++)
            if(i>=j)
                f[i][j]=f[i-j][j]+f[i-1][j-1];
    printf("%d\n",f[n][k]);
    return 0;
}

var
n,k,i,j:longint;
f:array[-200..200,-200..6]of longint;
begin
readln(n,k);
f[1,1]:=1;
for i:=2 to n do
for j:=1 to k do
f[i,j]:=f[i-1,j-1]+f[i-j,j];
writeln(f[n,k]);
end.
1. 解释一下DP方程
假设有4个数字，a,b,c,d
为了使状态不重复，所以，有俩种可能推到当前状态
1.在原来有序的基层上在前面加上一个1，即f[i,j]:=f[i-1,j-1]
2.在原来有序的基层上，集体都增加1，即f[i-j,j];（当前有j个数字）
这样可以始终保证序列有序，并且不会重复

Method 1:DP

#include<cstdio>
#include<iostream>

using namespace std;

int n, k, ans = 0;

int dp[201][7];
int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i <= n; i++) dp[i][1] = 1;
    for(int i = 2; i <= n; i++){
        for(int j = 2; j <= min(i, k); j++){
            dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
        }
    }
    printf("%d", dp[n][k]);
    return 0;
}

Method 2:dfs枚举

#include<cstdio>
#include<iostream>

using namespace std;

int n, k, ans = 0;

void dfs(int val, int am, int last){
    if(am == k){
        if(val == n)    ans++;
        return;
    }
    for(int i = last; i <= n-val; i++)
        dfs(val+i, am+1, i);
}

int main(){
    scanf("%d%d", &n, &k);
    dfs(0, 0, 1);
    printf("%d", ans);
    return 0;
}

#include<bits/stdc++.h>
using  namespace std;
typedef long long ll;
const ll N=50005;
ll i,j=0,m,n,k=0;
void yy(ll m,ll n)
{
    if(m==n||n==1)
    {
        k++;
        if(n==1)
        return;
        yy(m,n-1);
    }
    else
    {
        if(m<n)
            yy(m,m);
        else
        {
            yy(m-n,n);
            yy(m,n-1);
        }
    }
}
void xx(ll m,ll n)
{
    if(m==n)
    {
        k++;
        return;
    }
    else
        yy(m-n,n);
}
int main()
{
    cin>>m>>n;
    xx(m,n);
    cout<<k;
    return 0;
}

//递归也能做：）

数据比较水估计搜索递归也能过。
DP做法：
将整数i分成j份，对1进行讨论
若每份都大于1，即先将i分出j来使每份为1，问题转化为将剩下的i-j分成j份的问题
若至少有一份为1，1已经占了一份，问题转化为将i-1分成j-1份的问题
设f[i][j]表示数i分成j份的划分方案数，可得f[i][j]=f[i-j][j]+f[i-1][j-1]
~~~
#include <cstdio>
int n,k,f[205][8];
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) f[i][1]=1;
for(int i=2;i<=n;i++)
for(int j=2;j<=k&&j<=i;j++)
f[i][j]=f[i-1][j-1]+f[i-j][j];
printf("%d\n",f[n][k]);
return 0;
}

感谢楼下的楼下给的小提示。递归比较好理解- -
###block code
program ex;
var n,k:longint;
ans:int64;
procedure main(x,y,z:longint);
var num,i:longint;
begin
num:=x div y;
if y=1 then
begin
inc(ans); exit;
end;

for i:=z to num do
begin
main(x-i,y-1,i);
end;
end;

begin //main
read(n,k); ans:=0;
main(n,k,1);

write(ans);
end.

#include<cstdio>
int a[210][10];
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++) {
        a[i][1]=1;
        a[i][0]=0;
    }
    for(int i=2; i<=k; i++) {
        a[1][i]=0;
        a[0][i]=0;
    }
    for(int i=2; i<=n; i++)
        for(int j=2; j<=k; j++)
            if(j>i) a[i][j]=0;
            else a[i][j]=a[i-1][j-1]+a[i-j][j];
    printf("%d", a[n][k]);
    return 0;
}

#include <iostream>
#include <cmath>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <climits>  
#include <algorithm>  
using namespace std;

#define min(x,y) (x<y?x:y)

int sum=0;

void hh(int yy,int k,int u)
{
  if(yy==0){sum++;}
  else
  {
    for(int i=min(min(yy,k),u); i>=1; i--)
      {hh(yy-i,k,i);}
  }
}

int main()
{
  int n,k;
  cin>>n>>k;

  hh(n-k,k,k);

  cout<<sum;

  return 0;
}

暴力搜索竟然过了。。。
代码如下：
#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;

int ans = 0;
int n, k;
int vis[500];
int save[10];

void dfs(int tmp, int cnt)
{
if (cnt > k)
{
if (tmp == n)
{
ans++;
}
return;
}
for (int i = save[cnt - 1]; i < n; i++)
{
if (tmp + i <= n)
{
save[cnt] = i;
dfs(tmp + i, cnt + 1);
}
else
{
break;
}
}
}

int main()
{
cin >> n >> k;
save[0] = 1;
dfs(0, 1);
cout << ans<< endl;
system("pause");
return 0;
}

就是暴力枚举
#include<iostream>
#include<cstdio>
using namespace std;

int main()
{
int n,k,t=0,k1;
scanf("%d%d",&n,&k1);
if(k1==2){
for(int i=1;i<=n-k1+1;i++)
for(int j=1;j<=n-k1+1;j++)
if(i+j==n&&i>=j){
t++;
j = n-k1+2;
}
cout<<t;return 0;
}
if(k1==3){
for(int i=1;i<=n-k1+1;i++)
for(int j=1;j<=n-k1+1;j++)
for(int k=1;k<=n-k1+1;k++)
if(i+j+k==n&&i>=j&&j>=k){
t++;
k = n-k1+2;
}
cout<<t;return 0;
}
if(k1==4){
for(int i=1;i<=n-k1+1;i++)
for(int j=1;j<=n-k1+1;j++)
for(int k=1;k<=n-k1+1;k++)
for(int l=1;l<=n-k1+1;l++)
if(i+j+k+l==n&&i>=j&&j>=k&&k>=l)
{
t++;
l = n-k1+2;
}
cout<<t;return 0;
}
if(k1==5){
for(int i=1;i<=n-k1+1;i++)
for(int j=i;j<=n-k1+1;j++)
if(i+j<n)
for(int k=j;k<=n-k1+1;k++)
if(i+j+k<n)
for(int l=k;l<=n-k1+1;l++)
{
int u = n-i-j-k-l;
if(l<=u&&u>0)t++;
}
cout<<t;return 0;
}
if(k1==6){
for(int i=1;i<=n-k1+1;i++)
for(int j=i;j<=n-k1+1;j++)
if(i+j<n)
for(int k=j;k<=n-k1+1;k++)
if(i+j+k<n)
for(int l=k;l<=n-k1+1;l++)
if(i+j+k+l<n)
for(int u=l;u<=n-k1+1;u++)
{
int v=n-i-j-k-l-u;
if(u<=v) t++;
}
cout<<t;return 0;
}
return 0;
}

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int f[7][201][201], g[7][201];
int main() {
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        g[1][i] = 1;
    for(int i = 2; i <= k; i ++)
        for(int j = i; j <= n; j++) {
            for(int k = 1; k <= j / i; k++)
                f[i][j][k] = f[i][j][k - 1] + g[i - 1][j - k] - f[i - 1][j - k][k - 1];
            g[i][j] = f[i][j][j / i];
        }
    cout << g[k][n] << endl;
    return 0;
}

愚蠢的我只想到了n^2k的算法

#include<stdio.h>
int a=1,tot=0,n,k;
void aprt(int m,int n)
{
if(m>k)
{if(n==0)tot++;return ;}
if(n<0||n-k-1+m<0) return ;
for(int i=a;i<=n;i++)
{
a=i;
aprt(m+1,n-i);
}
}
int main()
{
scanf("%d%d",&n,&k);
aprt(1,n);
printf("%d",tot);
return 0;
}

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <ctime>
using namespace std;

int dg(int n,int k,int i)
{
    if (k==1) return 1;
    int ans=0;
    for(int z=i;z<=n/k;z++)
    {
        ans+=dg(n-z,k-1,z);
    }
    return ans;
}

int main()
{
    int a,b;
    cin>>a>>b;
    cout<<dg(a,b,1);
    return 0;
}

为毛我写了这么短......

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <ctime>
using namespace std;

int dg(int n,int k,int i)
{
if (k==1) return 1;
int ans=0;
for(int z=i;z<=n/k;z++)
{
ans+=dg(n-z,k-1,z);
}
return ans;
}

int main()
{
//clock_t go,end;
//go=clock();

//freopen(".in","r",stdin);
//freopen(".out","w",stdout);

int a,b;
cin>>a>>b;
cout<<dg(a,b,1);

//fclose(stdin);
//fclose(stdout);

//end=clock();
//cout<<(end-go);

return 0;
}

#include <iostream>

using namespace std;

int s;

int dfs(int n,int k,int l)
{
if(k==1){++s;return 0;}
int i;
for(i=l;i<=n;++i)
{
if((float)(n-i)/(k-1)<i)return 0;
dfs(n-i,k-1,i);
}
}

int main()
{
int n,k;
cin>>n>>k;
dfs(n,k,1);
cout<<s;
// system("pause");
return 0;
}

脑子里出现的第一个想法。应该算简单吧？
#include<iostream>
using namespace std;
int qqq(int n,int k)
{
if(n < k)
return 0;
if((n == k)||(k==1))
return 1;
if(n > k)
return qqq(n-1,k-1) + qqq(n-k,k);
}
int main()
{
int n,k;
cin >> n >> k;
cout << qqq(n,k);
return 0;
}

#include<cstdio>
int main()
{
scanf("%d%d",&m,&n);m-=n;
for(int i=1;i<=m;++i) f[1][i]=1;
for(int i=2;i<=n;++i)
{
f[i][0]=1;
for(int j=1;j<i;++j) f[i][j]=f[i-1][j];
for(int j=i;j<=m;++j) f[i][j]=f[i-1][j]+f[i][j-i];
}
printf("%d\n",f[n][m]);
}

这道题需要动归？
```c++
#include<iostream>
#include<cstdio>
using namespace std;

int n;
int k;

int dfs (int a, int b, int c) {
if (b == 1) return 1;
int res = 0;
int m = a / b;
for (int i = c; i <= m; i++) {
res += dfs (a - i, b - 1, i);
}
return res;
}

int main ()
{
//freopen ("in.txt", "r", stdin);
cin >> n >> k;
cout << dfs (n, k, 1);
return 0;
}
```

#include <stdio.h>
#include <string.h>

int f(int n,int k)//n个数分成k份
{
if(k>n)
return 0;
if(k==1)
return 1;
if(k==n)
return 1;
//最小的那个数是不是1
return f(n-k,k)/*不是，则每个数都比1大，可以全部-1*/+f(n-1,k-1)/*是，则可以转化为去掉那个1后分成k-1份*/;
}

int main()
{
int n,k;
scanf("%d%d",&n,&k);
printf("%d\n",f(n,k));
}

#水一发超短
#include<cstdio>
using namespace std;
int c[300][10];
int main() {
int n, k; scanf("%d%d", &n, &k); for(int i=1; i<=n; i++){ c[i][1] = 1; for(int j=2; j<=i&&j<=k; j++) c[i][j] = c[i-1][j-1] + c[i-j][j]; } printf("%d", c[n][k]);
return 0;
}