i****y
发帖数: 84 | 1 请问这道题能用dp解吗?单纯递归input大了以后很慢。。
网上还有Graham, Knuth, and Patashnik’s Concrete Mathematics解法，没看懂。。
。 | e*******8
发帖数: 94 | | g**G
发帖数: 767 | 3 cc150没看过，不知道题目是啥，不过我猜是有一堆1分，2分，5分。。。的硬币然后给
一个值让你求所有的组合数目？
如果是这个题的话，dp的话要用两个变量，建一个2维表，一个维度是钱数，一个维度
是硬币的种类
假设硬币为d1,d2,... dn, f(x，y)表示所有小于等于y的硬币可以组合成x的组合数目
f(x,y) = sigma(f (x-di), di) (i=1...n, di<=y)
integer partiion同理，只不过硬币变成1，2，3，4，5.。。。n而已 | i****y
发帖数: 84 | | i****y
发帖数: 84 | 5 谢谢
【在 g**G 的大作中提到】
: cc150没看过，不知道题目是啥，不过我猜是有一堆1分，2分，5分。。。的硬币然后给
: 一个值让你求所有的组合数目？
: 如果是这个题的话，dp的话要用两个变量，建一个2维表，一个维度是钱数，一个维度
: 是硬币的种类
: 假设硬币为d1,d2,... dn, f(x，y)表示所有小于等于y的硬币可以组合成x的组合数目
: f(x,y) = sigma(f (x-di), di) (i=1...n, di<=y)
: integer partiion同理，只不过硬币变成1，2，3，4，5.。。。n而已
|
|
