拆分数问题：将大小为 $n$ 的正整数拆分为若干无序的正整数的和的方案数。
感谢 @oy 对本文做出的巨大贡献（即吊锤 tth37）
动态规划一 $O(n^2)$
记 $f[i][j]$ 为将 $i$ 拆分为若干个大小不超过 $j$ 的整数的和的方案数。
分类讨论：第一种情况为 最大的拆分数恰好为 $j$，第二种为 最大的拆分数小于等于 $j-1$。对于第一种情况，可以强制拆分出一个 $j$，也可以考虑为将 $i-j$ 拆分，再强制插入一个 $j$ 所得到的方案数；对于第二种情况，直接套用定义 $f[i][j-1]$ 即可。
状态转移方程如下：
$$
f[i][j]=f[i-j][j]+f[i][j-1]
$$
动态规划二 $O(n^2)$
记 $g[i][j]$ 为将 $i$ 拆分为 $j$ 个整数的和的方案数。
分类讨论：第一种情况为 最小的拆分数恰好为 $1$，第二种为 最小的拆分数大于 $1$。对于第一种情况，可以强制拆分出一个 $1$，也可以考虑为将 $i-1$ 拆分，再强制插入一个 $1$ 所得到的方案数；对于第二种情况，不难发现在 $g[i-j][j]$ 的方案中 所有的拆分数都加上 $1$ 后，满足最小的拆分数大于 $1$ 并且所有拆分数之和恰好为 $i$，即为所求。
状态转移方程如下：
$$
g[i][j]=g[i-1][j-1]+g[i-j][j]
$$
动态规划三 $O(n\sqrt n)$
性质：在 $n$ 以下且大小超过 $\sqrt n$ 的数不超过 $\sqrt n$ 个。
考虑将 动态规划一 和 动态规划二 中的思想合并。
记 $f’[i][j]$ 仍为将 $i$ 拆分为若干个大小不超过 $j$ 的整数的和的方案数。唯一的区别是，我们只需将 $f’$ 数组的第二维循环到 $\sqrt n$ 即可。
记 $g’[i][j]$ 为将 $i$ 拆分为若干个整数的和的方案数，其中 大于等于 $\sqrt n$ 的数有 $j$ 个，对于这类数我们称之为 大数。
对 $g’$ 数组分类讨论：第一种情况为划分出 最小的大数恰好为 $\sqrt n$，另一种情况为 最小的大数大于 $\sqrt n$。对于第一种情况，可以强制拆分出一个 $\sqrt n$，也可以考虑为将 $i-\sqrt n$ 拆分，再强制插入一个 $\sqrt n$ 所得到的方案数；对于第二种情况，不难发现再 $g’[i][j]$ 的方案中 所有的大数都加上 $1$ 后，满足最小的 大数 大于 $\sqrt n$ 并且所有拆分数之和恰好为 $i$。
对于初值，$g[i][0]$ 显然为 $f[i][\sqrt n -1]$。
状态转移方程如下：
$$
g[i][0]=f[i][\sqrt n-1] \
g[i][j]=g[i-\sqrt n][j-1]+g[i-j][j]
$$