整数划分模型

整数划分模型

\(n\) 个数划分成 \(k\) 个的方案数

状态 \(f[i][j]\) 表示 将\(i\)划分为\(j\)的方案数

对于方案数，一般是由地推式子推的，

对于我们考虑最后一个盒子放的数为 \(1\) 或 \(!1\)，

那么最后一个数为 \(1\) 时，由于是第 \(j\) 列，那么他的方案数就是 \(j-1\)列的方案数，当前这一列就放一个，对于前面的方案数不受影响

即\(f[i-1][j-1]\)

当最后一位数是非 \(1\)时，\(1-j\) 每个数至少大于 \(1\)，如果将每个数都减一，方案数变吗，答案是不变

因为对于每种可能，\(1-j\) 上的数都是大于 \(1\) 的，那么减一并不会影响划分

\(f[i-j][j]\)

所以转移时为\(f[i][j]=f[i-1][j-1]+f[i-j][j]\)

\(n\) 个数划分成 \(k\) 个不相同的数的方案数

考虑最后一位为 \(1\) 的情况

上一个是 \(f[i-1][j-1]\) ，假若这个式子的方案数中有存在相同的 \(1\)，是不符合条件的

有第一个题的第二中情况同理可知

\(dp[i-j][j]\)可以转移答案，我令\(j=j-1\) ，那么式子成为 \(f[i-(j-1)][j-1]\), 前\(j-1\)的方案数是这个，那到\(j\)上就一个 \(1\)不会差生影响，就是从\(i\)拿个1而已

则有\(f[i-1-(j-1)][j]=f[i-j][j]\),注意这的第二唯，因为后面多了一个方一的盒子，所以\(j-1\)变成了\(j-1+1\)

为什么这样就没有重复的 \(1\) 呢，

因为这个式子(第一问第二种请狂)的原型是 \(f[i-j][j]\) 他是什么情况？，每一列上的数都是大于\(1\)的，我只不过最后面多加一个盒子（j+1），里面刚好放的是 \(1\)而已，前面的 \(j\)的盒子的数有\(1\)吗

所以式子为\(f[i][j]=f[i-j][j-1]+f[i-j][j]\)

就会这两个（逃