时间戳

首页 > 解决方案 > K sum的算法总结

algorithm - K sum的算法总结

问题描述

这是众所周知的Twelvefold way：

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

我们想在哪里找到以下方程的解数：

X1 + X2 + ... + XK = target

从给定的数组：

vector<int> vec(N);

我们可以假设 vec[i] > 0。有 3 种情况，例如

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

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

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

  2. Xi可以重复，解不能重复。

    2 个解决方案是 {1,2,2}, {1,1,3}

  3. Xi不能重复，解不能重复。

    0 解决方案。

ide 必须使用动态编程：

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的for循环：

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];
}

case 2 和 case 3 是这样吗？</p>

标签： algorithm

解决方案

在没有变量的解决方案中Kdp[i] 表示有多少解决方案可以实现 sum i。

包含变量K意味着我们为子问题添加了另一个维度。此维度不一定必须位于特定轴上。您的dp数组可能看起来像dp[i][k]或dp[k][i]。

  • dp[i][k]表示i使用k数字（重复或唯一）累积和的解决方案的数量
  • dp[k][i]意味着使用k数字多少个解决方案来累积总和i

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

推荐阅读