计数dp之整数划分

一个正整数 n 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。

我们将这样的一种表示称为正整数 n 的一种划分。

现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 10^9+7 取模。

数据范围

1≤n≤1000

输入样例:

5

输出样例：

7

思路：两种解法

第一种， 回想一下完全背包的思路，如下图，f（i，j）表示1 2 3 4 .....i中选，总体积为j的方案数，那么状态计算如下图

f(i,j)=f(i-1,j)+f(i-1,j-i)+f(i-1,j-i*2)+......+f(i-1,j-i*s)

f(i,j-1)=        f(i-1,j-i)+f(i-1,j-i*2)+......+f(i-1,j-i*s）

合并上面两个方程，所以f(i,j)=f(i-1,j)+f(i,j-i)

优化后f(j)=f(j)+f(j-i)

代码很短，但是理解本质还是有点难

完整代码：

#include <iostream>
using namespace std;
const int N=1010,mod=1e9+7;
int n,f[N];
int main(){
    cin>>n;
    f[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            f[j]= (f[j]+f[j-i])%mod;
    cout<<f[n];
}

第二种，f(i,j)表示所有总和是i，并且恰好表示成j个数的和的方案，这个状态表示就难在状态转移的计算上，如下图

结合f（i，j）的含义去理解

最小值是1时         f(i,j)=f(i-1,j-1)

最小值大于1时     f(i,j)=f(i-j,j)

完整代码：

#include <iostream>
using namespace std;
const int N=1010,mod=1e9+7;
int n,f[N][N];
int main(){
    cin>>n;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            f[i][j]= (f[i-1][j-1]+f[i-j][j])%mod;
    int res=0;
    for(int i=1;i<=n;i++)res=(res+f[n][i])%mod;
    cout<<res;
}