整数划分

原题链接：900. 整数划分 - AcWing题库

解题思路

解题方式：dp

整数划分很像完全背包问题

状态表示：二维：f[i][j]表示是否选i时，体积为j时的划分数量 一维：f[j]表示体积为j时的划分数量

属性：相加

状态转移：

二维：
f[i][j]可以由两种状态转移而来：
选i：
i选还是i，上次选了i上次就是这次的体积j减i，也就是j - i
不选i：
i不选就是i - 1，体积不变还是j
结合起来就是：f[i][j] = f[i - 1][j] + f[i][j - 1]

一维：
由于本层的结果只取决于上一层所以可以用f[j]表示，但是还是有两种情况：
选i：
上次选了i上次就是这次的体积j减i，也就是j - i
不选i：
体积不变，所以还是j
结合起来就是f[j] = f[j] + f[j - i]
还有一点因为体积j肯定要比待选数i大就要从i~n遍历

源代码

#include <iostream>
#include <cstdio>

using namespace std;

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

int n;
int 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];
    return 0;
}