整数划分（初级，中级，高级）

题目描述
使用递归编写一个程序，求一个正整数n的所有划分个数。
例如，输入3，输出3；输入4，输出5。
输入
多组输入，每一组是一个正整数n。
输出
输出划分数。
样例输入 Copy
3
4
样例输出 Copy
3
5

其实这种问题可以认为是把n划分为加数小于或等于某个数的划分，在这里把这个数成为m。例如，对6的划分可以认作是将6划分为加数小于等于6的划分，因为6的加数确实小于等于6，为什么要引入这个m呢，是因为我们发现，从这个角度思考，比较容易求解。我们将划分的种类数记为q（n,m）

在递归里，要对形参进行判断

（1）当n=1时 q(1,m)：表示是对1的划分，那么只有一种划分方式 1

（2）当m=1时q(n,1)：当m=1时其实就是把让所有加数小于等于1，那就是所有加数都是1咯（不考虑负数），当然也只有一种划分方式

（3）当n==m时q(n,n)：此时就是对n的划分出来的数没有限制，默认限制就是不大于n，此时划分的总类数要分两种情况才比较好解决：

    1.划分出来的数包含n（或m，因为n==m）:那只有一种方式 比如 6的划分 只有 6;一种方式
    
   2.划分出来的数不包含n（或m，因为n==m）:就可以认为是将6划分出来的数都小于6，其实就是都小于或等于5,接下来 其实就是求出来q(n,n-1)或者是q(n,m-1),此时n>m-1,放到递归方程里就是求解q(n,m) n>m

综合起来 q(n,n)=1+q(n,m-1)

（4）当n>m时：当遇到这个问题时，其实可以看做是对n的划分有了条件，就是所有的划分出来的数小于m，在上文中，6有11种划分方式，那是没有对6划分出来的数进行限制，当要使划分出来的数都小于某个数时比如5时，那就不是11种了。

5+1;

4+2,4+1+1;

3+3,3+2+1,3+1+1+1;

2+2+2,2+2+1+1,2+1+1+1+1;

1+1+1+1+1+1;

这个时候分两种情况：包含m和不包含m ：

不包含m就是：

4+2,4+1+1;

3+3,3+2+1,3+1+1+1;

2+2+2,2+2+1+1,2+1+1+1+1;

1+1+1+1+1+1;这些情况，其实就是求6的划分出来的数小于等于4的情况,放到递归方程就是 q(n,m-1)

包含m就是：

5+1;

这个时候，确定这种划分数量的时候m不再是主角，我们只要求出来n-m的划分情况就行了，因为此时的m的划分情况，取决于n-m。比如包含m=5的划分情况就是 6-5=1的情况，比如包含4的划分情况就是求6-4=2,2的没有限制的划分情况。放到递归方程里面就是q(n-m,m)

（5）q（n,m）n<m:n<m时，比如n=6,m=7 求得就是6得划分数小于等于7的情况，其实就是求解小于等于6，故此时情况就是求解q(n,n);

根据以上分析：

q( n, n ) = 1, 当 n ==1;

q( n, n ) = 1, 当m == 1;

q( n, n ) = q( n,n ) , 当n < m;

q( n, n ) = q( n, m-1) +1 , 当n == m;

q( n, n ) = q( n - m, m ) + q( n , m -1) , 当n > m;

1. 第一种做法（初级）

#include <bits/stdc++.h>
using namespace std;
int dp[5000][5000];
int main()
{
   
    int n;
    for (int i = 1; i <= 300; ++i)
        for (int j = 1; j <= 300; ++j)
        {
    //dp[i][j]表示把i划分为加数不大于j
            if (i == 1 || j == 1)
                dp[i][j] = 1;
            //如果把1分成j份那么只有一种，如果j为1，那么加数都是1，也只有一种
            else if (i < j)
                dp[i][j] = dp[i][i];
            //如果i<j，因为i的加数不可能大于i所以还是求加数不大于i的情况
            else if (i == j)
                dp[i][j] = 1 + dp[i][j - 1];
            //此时包含i的只有一种划分，那就是它本身，其余的都是不包含i的
            else
                dp[i][j] = dp[i - j][j] + dp[i][j - 1]; 
                //最后一种情况分为包含j的与不包含j的
        }
    while (cin >> n)
        cout << dp[n][n] << endl;
    return 0;
}

第二种做法（初级）递归

在这里感谢晖队（雅神）提供的帮助，下面附上大佬手工讲解图，结构清晰，一幕了然

偷偷附上晖队的博客
这是一个连续四场选拔赛都AK的大佬滴博客

#include <bits/stdc++.h>
using namespace std;
int dfs(int n, int all)
{
   
    if (all == 0)//all等于0的时候递归结束就加一
        return 1;
    int num = 0;
    for (int i = n; i >= 1; --i)
    {
   
        if (all >= i)//all一直在动态变化
            num += dfs(i, all - i);
    }
    return num;
}
int main()
{
   
    int n;
    while (cin >> n)
        cout << dfs(n, n) << endl;
    return 0;
}

如果数据不大也可以用另一种方法

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
int n, ans;
void dfs(int i, int s)
{
   
    if (s > n)
        return;
    if (s == n)
    {
   
        ans++;
        return;
    }
    for (i; i <= 10; i++) //保证每次加的数大于等于原来的
        dfs(i, s + i);
}
int main()
{
   
    int m;
    cin >> m;
    while (m--)
    {
   
        ans = 0;
        cin >> n;
        dfs(1, 0);
        cout << ans << endl;
    }
}

n划分成m个整数的和，dp[i][j]代表i划分成j个数（中级）

#include<bits/stdc++.h> 
using namespace std;  
int dp[105][108];  
int main()  
{
     
    int n,m,i,j,t;  
    dp[1][1]=1;  
    for(i=2; i<=100; i++)  
        for(j=1; j<=i; j++)  
        {
     
            if(i==j||j==1) dp[i][j]=1;  
            else dp[i][j]=dp[i-1][j-1]+dp[i-j][j];//含1和不含1 
        }  
    cin>>t;  
    while(t--)  
    {
     
        scanf("%d%d",&n,&m);  
        printf("%d\n",dp[n][m]);  
    }  
    return 0;  
}

方法二

#include <iostream>
using namespace std;
long long a[400][400];
int main()
{
   
    long long n, k;
    while (cin >> n >> k)
    {
   
        for (int i = 1; i <= n; i++)
            a[i][1] = 1;
        for (int j = 1; j <= k; j++)
            a[1][j] = 1;
        for (int i = 1; i <= n; i++)
        {
   
            for (int j = 1; j <= k; j++)
            {
   
                if (i < j)
                    a[i][j] = a[i][i];
                else if (i == j)
                    a[i][j] = a[i][j - 1] + 1;
                else if (i > j)
                    a[i][j] = a[i - j][j] + a[i][j - 1];
            }
        }
        cout << a[n][k] << endl;
    }
    return 0;
}

高级
题目：队花的烦恼
描述

ACM队队花C小+最近在X大OJ上做题，竟发现了一道做不出来的…水题！她快郁闷死了……也许是最近状态不太好吧……她希望大家能帮帮忙：把一个整数分成若干个不为零的整数，问有多少种不同分法。

例：7 3 其中的分法：1 1 5，1 5 1，5 1 1是同一种分法。

输入
有多组测试数据
每组数据都有两个整数n,m（6<=n<=500,2<=m<=6）
n表示该整数，m表示把n分成m份
输出
对每一组测试数据，输出不同的分法数
样例输入
7 3
10 2
20 3
样例输出
4
5
33
注意m<=6即可

#include<bits/stdc++.h> 
using namespace std;  
int dp[505][8];  
int main()  
{
     
    int n,m,i,j;  
    dp[1][1]=1;  
    for(i=2; i<=500; i++)  
        for(j=1; j<=i&&j<=6; j++)  
        {
     
            if(i==j||j==1) dp[i][j]=1;  
            else dp[i][j]=dp[i-1][j-1]+dp[i-j][j];  
        }  
    while(~scanf("%d%d",&n,&m))  
    {
     
        printf("%d\n",dp[n][m]);  
    }  
    return 0;  
}

类似的题目
将N（N<=50000）分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，{6} {1,5} {2,4} {1,2,3}，共4种。由于数据较大，输出Mod 10^9 + 7的结果即可。

开始想的dp[i][j]代表j的最大划分数不超过i，但是数组需要开很大。
换个思路就是dp[i][j]代表j划分成i个整数的方法数，也分有1还是没有1，跟上面第2题有点类似，但是还要求划分成不同的整数，所以方程为
dp[i][j]=dp[i][j-1]+dp[i-1][j-i] (有1且仅有1个1)
认真思考会发现i不会超过320，利用等差数列求和求出

#include <bits/stdc++.h>
using namespace std;
const int N = 50000;
const int mod = 1e9+7;
typedef long long LL;
LL dp[322][N+4];
int main()
{
   
    int n;
    for(int j = 1; j <= N; j++) dp[1][j] = 1;
    for(int i = 2; i <= 320; i++)
        for(int j = 1; j <= N; j++)
        {
   
            if(i >= j) continue;
            else dp[i][j] = (dp[i][j-i] + dp[i-1][j-i])%mod;
        }
    while(~scanf("%d", &n))
    {
   
        int sum = 0, ans = 0;
        for(int i = 1; i <= 320; i++)
        {
   
            ans = (ans + dp[i][n]) % mod;
        }
        printf("%d\n", ans);
    }
    return 0;
}

路漫漫其修远兮，吾将上下而求索