我想用n
个分区元素计算k
的整数分区。通过具有不同元素的给定向量v
定义可能的分区元素。分区元素可以选择多次。我怎样才能做到这一点?最优,无需迭代n
的所有整数分区。
示例:
n := 10
k := 3
v := 1,2,6,7,8
=> 3
典型的“硬币找零”问题。这是一个简单的动态编程。如果dp [a] [b]是a与b个硬币的分割数,则dp [a] [b] = dp [a-v [0]] [b-1] + ... + dp [ a-v [n-1]] [b-1],其中n是不同硬币的数量(在您的示例中,n = 5)
一种方法是让循环顺序按顺序考虑每个元素。
未存储的JavaScript:
function f(n, k, v, i=0){
if (k == 0)
return n == 0;
if (i == v.length)
return false;
let total = 0
while (k >= 0 && n >= 0){
total = total + f(n, k, v, i+1);
k = k - 1;
n = n - v[i];
}
return total;
}
console.log(f(10, 3, [1,2,6,7,8]));