整数拆分
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 的组合数)
具体组合方式同样可以得到