动态规划解决整数拆分

给定一个正整数，我们可以定义出下面公式：

N = a[1] + a[2] + a[3] + ... +a[m]；

a[i] > 0, 1<= m <= N；

对于一个正整数，求满足上面公式所有算式组合，如对于整数4：

4 = 4；

4 = 3 + 1；

4 = 2 + 2；

4 = 2 + 1 + 1；

4 = 1 + 1 + 1 + 1；

所以上面结果是5。

注意：对于"4 = 3 + 1"和 "4 = 1+ 3"，这两处实际上是同一种组合。

题解：采用动态规划法求f(n, n),利用二维数组求f(n, m)。这个函数的意思就是将n划分为最多m个整数有多少种组合。

根据n和m的关系，考虑下面几种情况：

（1）当n=1或者m=1时，只有一种划分。例如：将1划分为最多2个数只能是1=1或者将5划分为最多1个数5=5。

（2）当n=m时，根据划分中是否包含n，可以分为两种情况：

划分中包含n的情况，只有一个。例如：将4划分为4=1+1+1+1此时只有一种划分。
划分中不包含n的情况，此时划分的个数最多就是n-1；即f(n,n-1)。

（3）当n

（4）当n>m时，根据划分中是否包含m，可以分为两种：

当必须划分为m个数时，由于n>m。（这里就相当于有四个苹果要放入三个盘子，每个盘子至少要放一个苹果。）所以在划分的每一位上至少是1。即：f(n-m,m)。

当划分的个数不包括m时，即为：f(n,m-1)。

这里用4为例：

​
int main()
{ 
    int n = 0;
    scanf("%d",&n);
    int t[100][100];
    for (int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==1||j==1){
                t[i][j] = 1;
            }else{
                if(j==i){
                    t[i][j] = t[i][j-1]+1; 
                }else if(i