常量和組合的數量

Question

假設給出了n整數列表L1,L2,...,Ln和整數S。

我正在尋找一種方法來有效計數指數j1,j2,...,jn的組合，例如L1[j1]+L2[j2]+...+Ln[jn] = S。

舉一個例子，採取L1=[0,1,1,2], L2=[0,1], L3=[0,1,2,3,3]和S=4。 那麼可能的組合是

0+1+3 
0+1+3 
1+0+3 
1+0+3 
1+1+2 
1+0+3 
1+0+3 
1+1+2 
2+0+2 
2+1+1 

即我找的答案是10。

Answer 1

你可以用DP解決它。複雜性：O（nS）。

Count(i,s) = \sum_j=0..s Count(i-1,j) * Number of elements in list i with value (s-j) 

Answer 2

此問題已完成。您可以

1）蠻力它

，或者，如果你有一些額外的屬性（所涉及的總金額都較小，例如），你也可以考慮

2）使用動態規劃得到假多項式算法。