c++ - 大小为 k 且总和为 s 的子序列数

Question

标签： c++dynamic-programmingsubsequence

Answer 1

这可以使用背包方法解决。对于每个元素，您可以包含它或排除它。这是cpp代码：

ll knap(int values[],int n, int i, int length, int sum) { //ll is long long
    if(s<0 || i>n-1 ||l<0) return 0;
    if(s==0 && l==0) return 1;
    ll a = knap(values,n,i+1,l-1,s-values[i]); //including current element
    ll b = knap(values,n,i+1,l,s);  //not including the current element and moving on
    return (a+b);
}