动态规划：整数划分

这道题困扰了我整整三天，记录一下 😅

输入样例:

5

输出样例：

7

来源：acwing 900整数划分

要注意的一点是，这里边的划分，与顺序是没有关系的！例如5的划分2 + 3 和3 + 2 算作同一种划分~

思路一：

把1,2,3, … n分别看做n个物体的体积，这n个物体均无使用次数限制，问恰好能装满总体积为n的背包的总方案数（完全背包问题变形）

初值问题：

求最大值时，当都不选时，价值显然是 0 而求方案数时，当都不选时，方案数是 1（即前 i 个物品都不选的情况也是一种方案），所以需要初始化为 1, f[0][0] = 1 等价变形后： f[0] = 1

状态计算：

f[i][j]表示前i个整数（1,2…,i）恰好拼成j的方案数 求方案数：把集合选0个i，1个i，2个i，…全部加起来

c
f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] + ...;
f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2 * i] + ...;

因此 f[i][j]= f[i−1][j] + f[i][j - i] (这一步类似完全背包的推导）

朴素做法

c++
// f[i][j] = f[i - 1][j] + f[i][j - i]
#include <iostream>

using namespace std;

const int N = 1e3 + 7, MOD = 1e9 + 7;

int dp[N][N], n;

int main() {
    cin >> n;
    dp[0][0] = 1;

    for (int i = 1; i <= n; i ++) 
		{
        for (int j = i; j <= n; j ++) 
            dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % MOD;
    }

    cout << dp[n][n] << endl;
}

优化版：

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

const int N = 1e3 + 7, MOD = 1e9 + 7;

int dp[N], n;

int main() {
    cin >> n;
    dp[0] = 1;

    for (int i = 1; i <= n; i ++) 
		{
        for (int j = i; j <= n; j ++) 
            dp[j] = (dp[j] + dp[j - i]) % MOD;
    }

    cout << dp[n] << endl;
}

思路二：

状态表示： f[i][j]表示总和为 i ，总个数为 j 的方案数

状态转移方程： f[i][j] = f[i - 1][j - 1] + f[i - j][j]

代码：

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

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

int n;
int dp[N][N];

int main()
{
    cin >> n;

    dp[1][1] = 1;
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]) % mod;

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = (res + dp[n][i]) % mod;

    cout << res << endl;

    return 0;
}