https://loj.ac/problem/10018

题目描述

??求把\(n\)个整数分为\(k\)份，最多有多少种分法（顺序无影响）。

思路

??这道题是比较典型的\(dp\)题，但由于这道题的数据范围比较小，我这里主要想介绍\(dfs\)的做法及其剪枝。首先由于我们分解数字不需要顺序，所以我们可以假定分解数的下界为\(a[i-1]\)，并且我们已知将数分解\(a[1],a[2],...,a[i-1],\)剩余可分解的为\(m\)，那么\(a[i]\)的最大值为\(m/(k-i+1)\),因为剩余的全部平均划分即为\(a[i]\)的上界。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,s=0,a[10];
void dfs(int k)
{
    if(n==0)return ;
    if(k==m)
    {
        if(n>=a[k-1])s++;
        return ;
    }
    for(int i=a[k-1];i<=n/(m-k+1);i++)
    {
        a[k]=i;n-=i;
        dfs(k+1);
        n+=i;
    }
}
int main() 
{
    scanf("%d%d",&n,&m);
    a[0]=1;dfs(1);
    printf("%d",s);
    return 0;
}

数的划分

原文：https://www.cnblogs.com/fangbozhen/p/11760464.html