分析
题目要我求的其实就是n由几种组合方式,更直接来说就是求n可以由几个1,几个2,几个3···,到这里我们就发现这里很像完全背包问题了。
集合:f[i][j]表示由i种数字,组成的总和等于j的方案。
属性:方案数量
状态:f[i][j]=f[i-1][j]+f[i][j-1]
代码
1 | #include <iostream> |
另一种方法:
集合:f[i][j]表示数字和为i,由j个数字组成的方案数目
属性:数字为i的方案数量
状态:
状态转移方程:f[i][j]=f[i-1][j-1]+f[i-j][j]
代码
1 | #include <iostream> |
本文作者: jiangyuhao
本文链接: http://example.com/2022/04/16/%E6%95%B4%E6%95%B0%E5%88%92%E5%88%86/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!