狗狗店面

每个数字可以重复用吗？比如S=6时（3，3）算一个结果吗？

求组合数的话，用二维DP

wofaint 发表于 2018-11-10 17:41
问的就是组合数，不是所有组合

看错了， DP靠谱

大木虫 发表于 2018-11-10 22:52
求组合数的话，用二维DP

求个转移方程式子 谢谢大佬

dengzeyu147 发表于 2018-11-11 00:41
求个转移方程式子 谢谢大佬

我是这样想的，你看对不对
一个N 一个S，N是要用的数字的数量，S是目标和
转移可以从T(N-1, S-i)开始，0 <= i <= S
例如，T(5, 3) = T(4, 0) + T(4, 1) + T(4, 2) + T(4, 3)
T(4, 0)的每一个子答案添一个3 构成T(5, 3)一个子集
T(4, 1)的每一个子答案添一个2 构成T(5, 3)一个子集
T(4, 2)的每一个子答案添一个1 构成T(5, 3)一个子集
T(4, 3)的每一个子答案添一个0 构成T(5, 3)一个子集
合起来就是T(5, 3)

我感觉这题应该有公式解，找找规律没准能找出来。

AmyZhu 发表于 2018-11-9 12:18
由0...N的意思，比如N=5, 就是求(0,1,2,3,4,5)这里面所有组合加起来等于S。

那楼主你自己举的例子就错了吧？你说N = 2 S = 5,那就是求（0，1，2）这里面所有组合加起来等于5  组合数是多少呢？很混乱

EbyccoCheng 发表于 2018-11-10 00:30
从0-s间选n个数字 加起来等于s
可以用dp吧
sum（加起来等于s-i的n-1个数字的方式）

大佬能给个转移方程吗？

stzy 发表于 2018-11-10 18:03
每个数字可以重复用吗？比如S=6时（3，3）算一个结果吗？

应该都可以吧， 唯一区别就是dfs时是否包含当前值

dfs + memorize 吧，容易想到也好讲清楚

找工作啊找工作 发表于 2018-11-11 01:53
那楼主你自己举的例子就错了吧？你说N = 2 S = 5,那就是求（0，1，2）这里面所有组合加起来等于5  组合数 ...

抱歉，之前例子举得有问题。N就是说最后要的组合长度。比如N=3的话，S还是5，那么(0, 1, 4)就是一个有效的组合。