K和算法综述

Question

这是非常熟悉的Twelvefold way。

https://en.wikipedia.org/wiki/Twelvefold_way

其中，我们想要找到下列方程的解的数目：

X1 + X2 + ... + XK = target

从给定的数组中：

vector<int> vec(N);

我们可以假设veci > 0。例如，有3个案例

vec = {1,2,3}, target = 5, K = 3.

1. Xi可以重复，解决方案可以重复。

6解是{1,2,2}，{2，1}，{2,2,1}，{1,1,3}，{1,3,1}，{3，1}

1. Xi可以重复，解决方案不能重复。

2解为{1,2,2}，{1,1,3}

1. Xi不能重复，解决方案不能重复。

0解.

ides必须使用动态规划：

dp[i][k], the number of solution of target = i, K = k.

迭代关系是：

if(i > num[n-1]) dp[i][k] += dp[i-num[n-1]][k-1];

对于三种情况，它们依赖于i，n，k的运行顺序。当没有K的限制时，我知道结果(任意变量的和)：

案例1：

int KSum(vector<int>& vec, int target) {
    vector<int> dp(target + 1);
    dp[0] = 1;
    for (int i = 1; i <= target; ++i)
        for (int n = 0; n < vec.size(); n++)
            if (i >= vec[n]) dp[i] += dp[i - vec[n]];

    return dp.back();
}

案例2：

for (int n = 0; n < vec.size(); n++)
    for (int i = 1; i <= target; ++i)

案例3：

for (int n = 0; n < vec.size(); n++)
    for (int i = target; i >= 1; --i)

当有额外的变量k时，我们只是简单地添加for循环吗？

for(int k = 1; k <= K; k++)

在最外层？

编辑：

我尝试了案例1，只需在下面添加K的循环：

int KSum(vector<int> vec, int target, int K) {
    vector<vector<int>> dp(K+1,vector<int>(target + 1,0));
    dp[0][0] = 1;
    for (int n = 0; n < vec.size(); n++)
        for (int i = 1; i <= target; ++i)
            for (int k = 1; k <= K; k++)
            {
                if (i >= vec[n]) dp[k][i] += dp[k - 1][i - vec[n]];
            }

    return dp[K][target];
}

案例2和案例3是真的吗？

Answer 1

在没有变量的解决方案中，K dpi表示实现和i的解决方案有多少个。

包括变量K意味着我们在子问题中添加了另一个维度。这个维度不一定一定要在特定的轴上。您的dp数组可能看起来像dp[i][k]或dp[k][i]。

• dp[i][k]是指用k数累加和i的解数(重复或i表示使用k数)，以及累积和i

的解数。

两者都是一样的东西。这意味着您可以将循环添加到外部或内部。