7=1+1+5=1+2+4=1+3+3=2+2+3

每项减一：

4=1+3=2+2=1+1+2

所以f[n,k]:=f[n-k,k]+f[n-k,k-1]+f[n-k,k-2]+……+f[n-k,0]

其中，除f[0,0]:=1以外，对其余正整数n有f[n,0]:=0;

当j>i时，f:=0。

递推式

f:=f+f

应该分成有1和没有1的情况

f(i,j)表示i分成j份

f(i,j):=f(i-1,j-1)+f(i-j,j);

随便卡卡上界就可以搜过

想想dp怎么弄...

我直接递归试了下最后一个数据超了

不知道楼上用的是什么方法~~

直接递归哈!数据规模很小

有人能将清楚点吗？？

c(0,0):=1;

c(n,k):=c(n-k,k)+c(n-k,k-1)+...+c(n-k,0);

自然数无序分拆公式（设把n分为k份为c(n,k)）。

c(n,k):=c(n-k,k)+c(n-k,k-1)...+c(n-k,1);

c(n,1):=1;

c(n,2):=n div 2.

动态规划，以所分的数含不含1来递推，还是我的代码短^_^
#include<iostream>
#include<algorithm>
using namespace std;

int num[202][8];
int getNum(int n,int k){
if(n<k) return 0;
if(k==1 || n==k) return 1;
return num[n][k]=getNum(n-k,k)+getNum(n-1,k-1);
}

int main(){
int n,k;
cin>>n>>k;
cout<<getNum(n,k)<<endl;
return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=10000+10;
const int inf=0x3f3f3f3f;
const ll mod=7654321;
const double PI=3.1415926;
const double eps=1e-8;

int n,k;
ll f[201][10];
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>k;
    f[0][0]=1;
    FOR(i,n) FOR(j,k) {
        REP(l,0,j) if (i-l-(j-l)>=0) f[i][j]+=f[i-l-(j-l)][j-l];
        //cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
    }
    cout<<f[n][k]<<endl;
    
    return 0;
}

原来是s[k][n]的dp就够了啊，我用的是s[k][m][n]，多了一个最大值。状态是前K个数，最大值为m，和为n的组合数量。不过这个规模O(k*n^2)也不太需要去考虑时间了。

#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;
int n,k;
int f(int a,int b,int c)
{
    int g=0,i;
    if(b==1)
    g=1;
    else
    for(i=c;i<=a/b;i++)
    g+=f(a-i,b-1,i);
    return g;
}
int main()
{
    cin>>n>>k;
    cout<<f(n,k,1);
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
int f[200+1][6+1];

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

#include<iostream>
using namespace std;
long long n,k,ans;
void dfs(int t,int s,int b)
{
    int i;
    //if(n==200&&k==6)
    //ans=4132096;
    else
    {
    if(s==n&&t==k){
        ans++;
        return;
    }
    if(s==n||t==k) return;
    for(i=b;i<=n-s;i++)
    if(s+i<=n) dfs(t+1,s+i,i);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    dfs(0,0,1);
    cout<<ans;
    return 0;
}

#include<stdio.h>
#include<string.h>
#define fijk f[n][k][x]
int f[300][10][300];
int dijk(int n,int k,int x){
if(k==1) return fijk=1;
else if(~fijk) return fijk; fijk=0;
for(int i=x;i<=n/k;++i) fijk+=dijk(n-i,k-1,i);
return fijk;
}
int main(){
int n,k; scanf("%d%d",&n,&k);
memset(f,-1,sizeof f);
printf("%d\n",dijk(n,k,1));
}

#include<iostream>
using namespace std;
int fenjie(int n,int k,int a){
if(k==1){
return 1;
}
int m=0;
int q=n/k;
for(int i=a;i<=q;i++){
m+=fenjie(n-i,k-1,i);
}
return m;
}
int main(){
int n,k;
cin>>n>>k;
cout<<fenjie(n,k,1);
return 0;
}

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int n,k,ans=0;
int main()
{
    cin>>n>>k;
    if(k==2)
    {
        cout<<n/2<<endl;
    }
    if(k==3)
    {
        int a,b,c;
        for(int a=1;a<=n/3;a++)
            for(int b=a;b<=(n-a)/2;b++)
                for(int c=n-a-b;c>=b;c--)
                {
                    if(a+b+c==n)
                    ans++;
                }
        cout<<ans<<endl;
    }
    if(k==4)
    {
        int a,b,c,d;
        for(int a=1;a<=n/4;a++)
            for(int b=a;b<=(n-a)/3;b++)
                for(int c=b;c<=(n-a-b)/2;c++)
                    for(int d=n-a-b-c;d>=c;d--)
                    {
                        if(a+b+c+d==n)
                        ans++;
                    }
        cout<<ans<<endl;
    }
    if(k==5)
    {
        int a,b,c,d,e;
        for(int a=1;a<=n/5;a++)
            for(int b=a;b<=(n-a)/4;b++)
                for(int c=b;c<=(n-a-b)/3;c++)
                    for(int d=c;d<=(n-a-b-c)/2;d++)
                        for(int e=n-a-b-c-d;e>=d;e--)
                        {
                            if(a+b+c+d+e==n)
                            ans++;
                        }
        cout<<ans<<endl;
    }
        if(k==6)
    {
        int a,b,c,d,e,f;
        for(int a=1;a<=n/6;a++)
            for(int b=a;b<=(n-a)/5;b++)
                for(int c=b;c<=(n-a-b)/4;c++)
                    for(int d=c;d<=(n-a-b-c)/3;d++)
                        for(int e=d;e<=(n-a-b-c-d)/2;e++)
                            for(int f=n-a-b-c-d-e;f>=e;f--)
                            {
                                if(a+b+c+d+e+f==n)
                                ans++;
                            }
        cout<<ans<<endl;
    }
    return 0;
}

int main

好啊