狗狗店面

大木虫 发表于 2018-11-11 01:27
我是这样想的，你看对不对
一个N 一个S，N是要用的数字的数量，S是目标和
转移可以从T(N-1, S-i)开始， ...

嗯嗯！我是这样做的。

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

不算，不能duplicate

组合中可以包含重复数字么？比如N为2，S

补充内容 (2018-11-11 08:14):
抱歉没看到最新回复，请忽略

大木虫 发表于 2018-11-11 01:27
我是这样想的，你看对不对
一个N 一个S，N是要用的数字的数量，S是目标和
转移可以从T(N-1, S-i)开始， ...

感觉这题没这么简单，因为组合里不能用duplicate。。
对于N=1, 每个S只有一种组合， 即 T(1, i) = 1,  0 <= i <= S.
那么T(2, i) = SumOf(T[1,0] ... T[1,i])= (i + 1) * 1;  也就是T(2, i) = i + 1,   0 <= i <= S.
T(2, 5) = 6 是对的结果，但是 T(2，2) = 3 就好像有点问题， 根据题意只有两个组合是合法的 (0, 2）和 (2, 0), 而(1, 1)有duplicate不能算进去:(

   觉得按楼主的意思 应该得这么dp
T（idx，sum，count） = T（idx-1，sum，count） + T（idx-1，sum-idx,count-1）