题目描述

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

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

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

算法1

多重背包

将问题转化为：
物品体积为1,2,3…n, 背包总体积为n, 求恰好装满背包的方案数

多重背包朴素版

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, mod = 1e9 + 7 ;

int f[N][N];// 1 - i中选恰好组成j的方案的集合

int main()
{
    int n;
    cin >> n;

    f[0][0] = 1;

    for(int i = 1 ; i <= n ; ++i){
        for(int j = 0 ;  j <= n ; ++j){
            for(int k = 0;i * k <= j; ++k){//k取0的情况可以表示不取i 这样状态表示可以做到不重不漏 
                f[i][j] = (f[i][j] + f[i - 1][j - k * i]) % mod;
            }
        }
    }

    cout << f[n][n] << endl;
    return 0;
}

多重背包滚动数组优化

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N];

int main()
{
    int n;
    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] << endl;
    return 0;
}

算法2

分析：将所有情况分成两种
1.将i划分为j个数后，j个数中的最小值为1
2.将i划分为j个数后，j个数中的最小值不为1

状态表示：f[i][j] 表示将i划分成j个数的方案的集合
属性：Count
状态计算：

// 1.将i划分为j个数后，j个数中的最小值为1
f[i][j] = f[i - 1][j - 1];// 将i - 1 划分为j - 1个数 再加上最小值1 就可以表示所有方案

// 2.将i划分为j个数后，j个数中的最小值不为1
f[i][j] = f[i - j][j];
/*
由于j个数中的所有值都大于1，因此将每一个数减去一就可以得到将i - j划分为j个数的一种方案。
由于方案中的数字都是一一对应的 (x - 1 <-> x)，因此两种情况下的方案数是完全相等的，可以直接转移过来。
*/

计数dp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1010, mod = 1e9+7;
int f[N][N];


int main()
{
    int n;
    cin >> n;

    for(int i = 0 ; i <= n ;++i)f[i][1] = 1;

    for(int i = 1; i <= n  ;++i){
        for(int j = 1; j<= n ;++j){
            if(i >= j)f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
        }
    }

    LL res = 0;
    for(int i = 1; i <= n  ;++i)res = (res + f[n][i]) % mod;// 统计答案时需要统计将n划分为i个数的所有情况并相加

    cout << res << endl;
    return 0;
}