我的理解是1很特殊
在这个题目上确实很巧妙
但是下次遇到什么样的DP会再次使用这种思路呢？
by _farawaystar_ @ 2023-09-29 22:45:56
多练。
by Lovely_Cat_WBB @ 2023-09-29 23:00:15
我认为可以归类到所谓“提前计算”思想，如果有一个 1 那么干掉，否则**提前**在所有 $k$ 份中放进去一个 $1$ 变成子问题。
by yukimianyan @ 2023-09-29 23:08:29
一车 DP 都需要“提前计算”思想优化，例如斜率优化的模板题。然后在容斥那边有一个问题也有应用（将 $n$ 个相同的小球放入 $m$ 个互不相同的盒子里，要求每个盒子最少 $1$ 个最多 $k$ 个的方案数。呃呃呃应该算吧）
by yukimianyan @ 2023-09-29 23:10:22
@[yukimianyan](/user/509229) wait
谢谢您，但是这个和斜率优化的提前计算也有关系吗？
（貌似我理解不到位了唉
by _farawaystar_ @ 2023-09-29 23:44:19
@[yukimianyan](/user/509229) 方便给一下您说得容斥那个题目的题号吗？我去钻研一下
by _farawaystar_ @ 2023-09-29 23:46:32
我还做过一题可以有0的
就是f[i][j]=f[i-j][j]+f[****i****][j-1]
按有0与没有0分
区别是加粗部分
so,我认为可能就是题目中特殊的情况
多练（我一开始也想不到哇QAQ)
by dusty__zzy @ 2023-10-20 17:39:21
@[_farawaystar_](/user/370037)
我觉得根本的原因就是这个题目对划分数最小的限制是1
一种情况是不含1，但其实可以每一个划分数都可以看作是1+另一个划分数。那么这时候就可以看作是是dp[i-k][k]的全部划分数全部加上1，全体加上一就是唯一确定的情况。所以可以得到其中一种转移情况。
另外一种情况就是起码含有一个1，那么此时去掉这个1，就表明由1变为了0，而0就相当于少了一个划分数，所以是dp[i-1][k-1]。
为什么dp[i][k]可以看作这两者之和呢，因为这两种情况是明显互斥的，不含1和起码含一个1，明显这两者是互斥的，所以dp[i][k]的状态转移方程就是这两种子问题的解的并集。本质上还是解空间的思想。
1不是特殊的，如果这道题最小划分数的限制换成3，解空间就能由起码有一个3的解集和没3的解集构成。因为这两种情况也是互斥的，只是转移状态方程会变得非常复杂，你需要统计其小于三的拆分数的数量和这些拆分数加起来的总和才能写出来这个状态转移方程。所以1在这里只是利用了题目对拆分数最小限制为1从而简化了状态转移方程而已。
@[dusty__zzy](/user/626129) 就好像这位大佬做过一道可以有0的题目，恰恰就是以有没有0来分，因为0为最小划分数，可以简化状态转移方程，而1就不行。这说明了1并不特殊，特殊的是最小划分数(能被视作一个划分数的最小值)这个限制。
by Operation0701 @ 2023-11-18 21:16:21
@[Operation0701](/user/1170071) /ll
谢谢您这么耐心的解答
可就在今天我已经退役了/ll
by _farawaystar_ @ 2023-11-18 21:49:45
@[_farawaystar_](/user/370037)
您刚刚退役，而我却刚刚开始接触算法。
您有机会去打竞赛，而我却没有机会。
也许这就是人与人之间不同的时区吧。
by Operation0701 @ 2023-11-18 22:04:18