问题描述：将整数n分成k份，且每份不能为空，任意两个方案不能相同(不考虑顺序)。

输出：一个整数，即不同的分法。

示例

输入：7,3

返回值：4

说明：整数7分为3份有4种办法:[1,1,5][1,2,4][1,3,3][2,2,3]    

      使用动态规划的办法进行分析，本题可以类比将$n$个小球放入$k$个盒子中，小球、盒子无差别，且盒子不能为空。设置将$n$个小球放入$k$个盒子中方法为$f[n][k]$，因此为了使每个盒子中不为空，先拿出$k$个小球分别分别放到每个盒子中，再将$n-k$个小球放入$k$个盒子中，其方法数为$f[n-k][k]$；或者保证每个盒子至少有一个小球，先将1个小球放入1个盒子中，剩余的$n-1$个小球放入$k-1$个盒子中其方法数为$f[n-1][k-1]$，因此总的方法数为$f[n][k]= f[n-k][k]+ f[n-1][k-1]$。具体步骤如下：

• 设置$f[n][k]$为整数$n$分成$k$份，且每份不能为空的方法数
• 其转移方程为$f[n][k]=f[n-k][k]+f[n-1][k-1]$
• 初始化$f[0][0]=1$，只有当$n$大于等于$k$才可进行划分。

图解

输入：5，3

返回值：2

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
        int mod=1000000007;
    int divideNumber(int n, int k) {
        // write code here
        if(n<k) return 0;
        vector<vector<int>> f(n+1,vector<int>(k+1));
        f[0][0]=1;//初始化
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=k;j++)
            {
                if(i>=j)//类比小球数量必须大于盒子数量k
                   f[i][j]=(f[i-1][j-1]+f[i-j][j])%mod;
            }
        }
        return f[n][k];
    }
};

• 时间复杂度：设置内外两层嵌套循环，外层循环次数为$n$，内层循环次数$k$，因此总的时间复杂度为$O(n*k)$
• 空间复杂度：借助于一个二维数组$f[n][k]$用于存放整数$n$分成$k$份，且每份不能为空的方法数，因此空间复杂度为$O(n*k)$

     直接采用暴力搜索的办法，对于一个整数，首次分配我们可以分配1，2，...，接着如果选定第一次分配1，那么第二次可以分配1，2，...，一直往下，直到所有的分配数之和为整数n，分配次数为k，此时这是一种分配的方案数。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    int depth;
    int sum;//存储划分方案数
    int divideNumber(int n, int k) {
        // write code hereif
        depth=k;
        sum=0;
        if(n<k) return 0;
        search(0,n,1);//第一个参数表示搜索的深度层数，第二个参数表示整数n的剩余数，第三个参数表示分配数开始的数，由于不能为空，因此开始为1
        return sum;
        
        
    }
    void search(int dep,int res,int start)
    {
        if(dep==depth+1)
        {
            if(res==0)//整数n已经分配完成，是一种分配方案
                sum++;
            return;
        }
        for(int i=start;i<=res;i++)//继续向下搜索，并且层数+1，n剩余的数需要减去开始的数
        {
            search(dep+1,res-i,i);
        }
    }
    
};

• 时间复杂度：将整数$n$分为$k$个，且每个不能为空，可类比为将$n$个小球使用挡板隔开，挡板数为$k-1$，需要的操作为，因此时间复杂度为
• 空间复杂度：每次递归的空间为$O(1)$，共递归$k$次，因此空间复杂度为$O(k)$