Problem Description
“Well, it seems the first problem is too easy. I will let you know how foolish you are later.” feng5166 says.

“The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+…+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that “4 = 3 + 1” and “4 = 1 + 3” is the same in this problem. Now, you do it!”

Input
The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.

Output
For each test case, you have to output a line contains an integer P which indicate the different equations you have found.

Sample Input
4
10
20

Sample Output
5
42
627

思路：这个就是整数的划分问题，定义f(i,j)表示数字 i 用最大系数 j 来表示的所有种数。
f(1,m) = f(m,1) = 1 。数字1只一种表示，即本身。数字m用1表示也只有一种即1 + 1 + 1 +…+ 1 = m。
这样边界条件就处理好了，最主要是f(i,j) i > j 怎么处理，f(i,j) = f(i,j-1) + f(i-j,j).举个例子，f(4,2) 可以是f(4,1) + f(2,2)。f(4,1)就是说4 除了用2来表示还可以用1来表示，f(2,2)表示4用2 表示为什么要4-2呢相当于拿出来了一项2，把问题规模缩小，现在变成f(2,2)了，实际是上2+f(2,2)，也就是2 + 2 或者2 + 1 + 1，这样子的。如果理解了这个转移那么剩下的问题就很简单了。考虑 f(i,j) i = j 。f(i,j) = 1 + f(i,j-1).
数字i，可以用i + 0表示这是一种可能，剩下的可能我就从子问题来求解就好了。比如f(2,2) = 1 + f(2,1)。意思是 （2 + 0 ） + f(2,1).而f(2,1)可以从上面递推式求解。那么由于f(i , j) = f(i,j-1) + f(i-j,j).可能会存在f(i,j) j>i。这种情况直接令其等于 f(i,j) i = j，就好了，因为i是 > 0的。
这里用了数组记忆化，防止超时。
转移方程：

代码：

#include<iostream>
#include<ctime>
using namespace std;

//f(n,m)整数n用最大系数m划分的种数
const int maxn = 1100;
int dp[maxn][maxn]; 
int f(int n,int m){
	if(dp[n][m]>0)return dp[n][m];
    if(n == 1 || m == 1)return dp[n][m];
    if(n == m)return dp[n][m] = 1+(dp[n][m-1]=f(n,m-1));
    else if(m > n)return dp[n][n]=f(n,n);
    else return (dp[n][m-1]=f(n,m-1))+(dp[n-m][m]=f(n-m,m));
}
int main(){
    int n;
    dp[1][1] = 1;
    for(int i=1;i<=maxn;i++){
    	dp[i][1]=1;
    	dp[1][i]=1;
	}
	f(1100,1100);
    while(cin>>n){
        cout<<dp[n][n]<<endl;
    }
}

打印分解结果

#include<bits/stdc++.h>
using namespace std;

int a[100];
int res;
void dfs(int l,int r,int n){
	for(int i = 1;i <= min(l,r);i ++){
		a[n] = i;
		if(l == i){
			cout<<res<<" = "<<a[1];
			for(int i = 2; i <= n ; i++){
				cout<<" + "<<a[i];
			}
			cout<<endl;return ;
		}
		dfs(l-i,i,n+1);
	}
}
int main(){
	int n = 10;res = n;
	dfs(10,10,1);
}