状态转移方程（集合划分）：

dp[n][k] = dp[n][k-1] + dp[n-k][k] 1 这个方程的含义是：整数 n 的划分可以分为两类：

不包含任何 k 的划分。 包含至少一个 k 的划分。 对于第一类，即整数 n 的所有不包含 k 的划分数量，这就相当于 dp[n][k-1]。对于第二类，我们可以先取一个 k，然后计算剩余部分 n-k 的划分数量，这就是 dp[n-k][k]。

基于上述思路，动态规划的过程如下：

初始化：没有初始化的思路就看看转移方程，最初始是什么样子dp[1][1] = dp[1][0] + dp[0][1]，然后在思考一下这些代表的含义：dp[1][1]即整数1，使用不大于1的整数，的可能划分方法数量。dp[1][0]即整数1，使用不大于0的整数，的可能划分方法数量。dp[0][1]即整数0，使用不大于1的整数，的可能划分方法数量。显然dp[1][0]不存在，即为0。dp[0][1]永远为1，即不选这一种情况。同理得出dp[0][i]=1，这就是初始化。

填表：按照从小到大的顺序填写 dp 表。对于每个 n（从 1 到目标整数）和每个 k（从 1 到 n），根据状态转移方程计算 dp[n][k] 的值。

结果获取：整数 n 的划分数量等于 dp[n][n]，因为这表示使用不大于 n 的所有正整数的划分方式数量。

举例来说，如果我们要计算 4 的划分数量，我们会计算出以下的 dp 表：

n\k | 1 2 3 4

1 | 1 1 1 1 2 | 1 2 2 2 3 | 1 2 3 3 4 | 1 3 4 5 1 2 3 4 5 6 从表中可以看出，整数 4 的划分数量是 5，对应于 dp[4][4] 的值。

通过这种自底向上的方式，动态规划不仅能够解决整数划分问题，还能够有效地处理更复杂的变体，例如限制划分中数字的最大值、最小值或者特定的数字集合等。

让我们再来看看状态转移这个方程：dp[n][k] = dp[n][k-1] + dp[n-k][k]。思考一下能不能优化？

交换一下n,k试试：dp[k][n] = dp[k-1][n] + dp[k][n-k]。有没有发现它的第一维，分别是k,k-1,k，在二维表格中，第一维其实就是每一层嘛，也就是说第k层的至多用到了k-1层和k层的数据，咱们是不是可以使用滚动数组来优化嘞。

C++代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=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])%M;
        }
    }
    cout<<f[n];
}