整数拆分

Integer partition / Coin Change Problem (Algorithm) Dynamic Programming (Discrete Math)

x 轴上面的数字: 最终组合成的值
Y 轴左边的数字:包含的硬币面值
中间填充值:组合次数

用 0,1,2,3,4,5 拼成 5 的组合数等于用 0,1,2,3,4 拼成 5 的组合数再加 1(单个 5);

用 0,1,2,3,4 拼成 5 的组合数等于用 0,1,2,3 拼成 5 的组合数加用 0,1,2,3,4 拼成 1(5-4) 的组合数

用 0,1,2,3 拼成 5 的组合数等于用 0,1,2 拼成 5 的组合数加用 0,1,2,3 拼成 2(5-3) 的组合数。
// 不使用 3 的组合数 + 使用 3 的组合数(即用 0,1,2,3 拼成 2 的组合数)

具体组合方式同样可以得到