简单整数划分（递归法+动态规划法）

整数划分：

所谓整数划分，就是将一个数n写成正整数相加的形式，如3可以划分为1+1+1，1+2，3等三种情况，而f（n,m）则表示，划分数中最大的数小于m时n的划分。如f（3,2）就是1+1+1,1+2两种。

递归法：

根据n和m的情况，有如下几种情况

1.当n == 1或m == 1时，都只有一种划分，其中n==1时，只有一种划分{1}，只有m == 1时，只有一种划分{1,1,1…..,1};即n个1。

2.由于划分中没有负数，所以当n < 1或m < 1时，都只有0种划分。

3.当n < m时，由于没有负数，所以f(n,m)就相当于f(n,n);

4.当n == m时，可以分为两种情况：

(1).划分中有n即只有{n}一种情况。

(2).划分中没有n即划分中最大值小于等于n-1，即n对于n-1的所有划分。

所以综上，n == m时，f(n,n) == f(n,n-1)+1;

5.当n > m时，可以分为两种情况：

(1).划分中包含最大值m的情况，即{m,{x1,x2…..}}，而在{x1,x2…..}，也就是n-m中同样可能大于m，所以为n-m对于m的划分，即f(n-m,m);

(2).划分中不包含m，同情况4，所有值比m小，即f(n,m-1);

综上，f(n-m,m)+f(n,m-1)。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int query(int n,int m)
{
    if(n == 1||m == 1)  return 1;
    if(n < 1||m < 1)    return 0;
    if(n < m)   return query(n,n);
    if(n == m)  return query(n,m-1)+1;
    if(n > m)   return query(n-m,m)+query(n,m-1);
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        cout<<"递归:"<<query(n,n)<<endl;
    }
    return 0;
}

动态规划法：

在递归法中的1,2情况都可以直接通过初始化dp数组来进行处理，而情况3,4,5则转换成动态转移方程就可以了。

转移方程：dp[n][m] += dp[i][j-1]+dp[i-j][j];

(当i-j < j时)dp[n][m] += dp[i][j-1]+dp[i-j][i-j];

#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int main()
{
    int n;
    int dp[550][550];
    dp[1][1] = 1;
    for(int i = 2;i <= N; i++){dp[i][1] = 1;dp[i][i] = 1;}

    for(int i = 2;i <= N; i++)
    {
        for(int j = 2;j <= i; j++)
        {
            if(i-j < j) dp[i][j] += dp[i][j-1]+dp[i-j][i-j];
            else dp[i][j] += dp[i][j-1]+dp[i-j][j];
        }
    }
    while(~scanf("%d",&n))
        cout<<"dp:"<<dp[n][n]<<endl;
    return 0;
}