数的划分

数的划分

$转载洛谷dfs暴力模拟过程$转载洛谷dfs暴力模拟过程

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,k,cnt=0;
void dfs(int last,int sum,int cp){
    if(cp==k){
        if(sum==n) {cnt++;}
        return ;
    }
    for(int i=last;i<=n-sum;i++){
        dfs(i,sum+i,cp+1);
    }
}
int main(){
    scanf("%d%d",&n,&k);
    dfs(1,0,0);
    cout<<cnt<<endl;
    return 0;
}

$转载洛谷dp过程$转载洛谷dp过程

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,k,dp[205][8];
int main(){
    scanf("%d%d",&n,&k);
    dp[1][1]=1;
    for(int i=2;i<=n;i++){
    dp[i][1]=1;
    for(int j=2;j<=k&&i>=j;j++){
        dp[i][j]=dp[i-1][j-1]+dp[i-j][j];
    }
    }
    cout<<dp[n][k]<<endl;
    return 0;
}