简单的整数划分问题 （不一样的解法 通俗易懂）

解法 通俗易懂）"/>

简单的整数划分问题 （不一样的解法 通俗易懂）

将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。

输入
标准的输入包含若干组测试数据。每组测试数据是一个整数N(0 < N <= 50)。
输出
对于每组测试数据，输出N的划分数。
样例输入

5

样例输出

7

提示

5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

这道题相信很多人都看过一个特别好的解，虽然有点难懂，但认真看一看还是可以看懂的。在百度百科中也有介绍整数划分
那种方法我就不说了。今天我来讲一个不一样的解法。请耐心看到最后。
首先做法类似，我们记n的包含m划分的个数为f(n,m) ,但这里的m就是构成n的最大值。也就是说在一系列数之和为n中必须出现m.
例如f(5,4)=1，因为 只有 5=4+1，所以只有一种.
然后我们再进行分类讨论：

• 1 若m>n，那么f(n,m)=0,因为m不可能构成n
• 2 若m=n，那么f(n,m)=1,因为只有一种 m=n
• 3.若m<n，就比较复杂需要讨论一下了。开始我以为就是f(n-m,m),其实不是，因为当m>n-m,f(n-m,m)=0,这样就导致f(n,m)=0,这样很明显是不正确的。重理思路，我们再看，在构成n-m的一串数字中它的最大值是m吗？不一定吧，可以是1-m的任意一个。那么f(n-m,m)就应该是这些情况的和。也就是:
  f(n-m,m)= ( ∑ k = 1 m f ( n − m , k ) ) \displaystyle \left( \sum_{k=1}^m f(n-m,k) \right) (k=1∑m​f(n−m,k))；

最后的结果肯定是：
ans= ( ∑ m = 1 n f ( n , m ) ) \displaystyle \left( \sum_{m=1}^n f(n,m) \right) (m=1∑n​f(n,m))；
然后就直接计算就好了，贴代码吧

#include<cstdio>
#include<cmath>
using namespace std;
int f[55][55] = {0};
int ans[55]= {0};
//分类讨论并计算,把m看成构成n的一系列数中最大的一个
int F(int n,int m)
{int res = 0;if(n<m)ans = 0;if(m==n)ans= 1;else if(m<n)//这里for(int i = 1; i<=m; ++i)ans += f[n-m][i];return ans;
}
void Caculate()
{
//    计算f[n][m]for(int n = 1; n<=50; ++n)for(int m = 1; m<=50; ++m)f[n][m] = F(n,m);//保存结果for(int n = 1; n<=50; ++n)for(int i = 1; i<=n; ++i)ans[n] += f[n][i];
}
int main()
{
//    freopen("out.txt","w",stdout);Caculate();int n;while(~scanf("%d",&n))printf("%d\n",ans[n]);return 0;
}

虽然以前学过这个问题的解法，但是刚好忘记了m的意义，又不想百度，然后误打误撞想出了这个解法。欢迎交流。