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
1.递归法:
根据n和m的关系,考虑以下几种情况:
(1)当n=1时,不论m的值为多少(m>0),只有一种划分即{1};
(2) 当m=1时,不论n的值为多少,只有一种划分即n个1,{1,1,1,…,1};
(3) 当n=m时,根据划分中是否包含n,可以分为两种情况:
(a). 划分中包含n的情况,只有一个即{n}; (b). 划分中不包含n的情况,这时划分中最大的数字也一定比n小,即n的所有(n-1)划分。 因此 f(n,n) =1 + f(n,n-1);(4) 当n< m时,由于划分中不可能出现负数,因此就相当于f(n,n);
(5) 但n>m时,根据划分中是否包含最大值m,可以分为两种情况:
(a). 划分中包含m的情况,即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m,因此这种情况下为f(n-m,m) (b). 划分中不包含m的情况,则划分中所有值都比m小,即n的(m-1)划分,个数为f(n,m-1);因此 f(n, m) = f(n-m, m)+f(n,m-1);综上所述:
f(n,m)=1; (n=1 or m=1) f(n,m)=f(n, n); (n<m) f(n,m)=1+ f(n, m-1); (n=m) f(n,m)=f(n-m,m)+f(n,m-1); (n>m)2.动态规划
状态转移方程:
当 n == 1 || k == 1 时,f(n, k) == 1, n为1,那么只能为1; 而k为1,那么只能划分成n个1.
当 n < k 时,f(n, k) == f(n, n),因为n的划分中不可能出现比n大的数,所以可以将最大值从k降到n;
当 n >= k 时,f(n, k) = f(n-k, k) + f(n, k-1), 前半部分是划分中存在最大值k,所以可以在(n-k)中继续以最大值为k来划分,而后半部分则是划分中最大值不是k,那么其结果和以(k-1)为最大值的划分是一样的。在初始化中可以将f(0, k)初始化为1,及对应f(n, n)可能出现的情况。
综合来说,使用递归更加容易理解,不过使用动态规划时间消耗更小。
#include<iostream> using namespace std; long long d[125][125]; void dp() { for(int i=1;i<=120;i++) d[i][1]=d[1][i]=d[0][i]=1; for(int i=2;i<=120;i++) for(int j=2;j<=120;j++) { if(i<j) d[i][j]=d[i][i]; else d[i][j]=d[i-j][j]+d[i][j-1]; } } int main() { int n; dp(); while(cin>>n) cout<<d[n][n]<<endl; return 0; }