89 k数和

原题网址：https://www.lintcode.com/problem/k-sum/description

描述

给定n个不同的正整数，整数k（k < = n）以及一个目标数字。　

在这n个数里面找出K个数，使得这K个数的和等于目标数字，求问有多少种方案？

您在真实的面试中是否遇到过这个题？是

样例

给出[1,2,3,4]，k=， target=，[1,4] and [2,3]是个符合要求的方案

标签

动态规划(DP)

思路：最开始参照了k数和Ⅱ用递归来做，结果只通过18%的数据就Time Limit Exceeded了。点开标签一看，要用动态规划……一口老血。

好吧，动态规划就动态规划。刚做过背包问题，背包问题中用背包容量作为动态数组一个维度，另一个维度是取0~i个物体，dp值是当前最大容量。而这道题，目标数字相当于背包容量，要作为一个维度，但与背包问题不同的是，这道题是从前 i 个中取出若干个（j），又多出一个维度，所以要用三维动态数组，dp值表示当前方案数，大爷的……

也就是说，dp【i】【j】【t】表示从前i个数中取出j个，这些数的和要等于t，有多少种方案。

状态转移方程：dp【i】【j】【k】=dp【i-1】【j】【t】+dp【i-1】【j-1】【t-A【i】】（当然前提是t>=A【i】）；

即

                    dp[i][j][t]=dp[i-][j][t];

                    if (t>=A[i])//注意是大于等于;

                    {

                        dp[i][j][t]+=dp[i-][j-][t-A[i]];

                    }

意思就是，每个元素都有两种状态，取或者不取：

（1）若不取A[i]这个值，当前方案数等于从前i-1个数中取j个使其和为t的方案数，即dp[i - 1][j][t]。

（2）若取当前值A[i]，则当前方案数等于从前i-1个数中取j个使其和为t的方案数再加上考虑A[i]的情况，即dp[i - 1][j - 1][t - A[i]]（前提是t - A[i]要大于等于0）。

值得注意的是，如果j为0并且t也为0，则dp【i】【j】【t】=1，即是说从任意集合里拿出0个数使其和为0，这种情况只有一种方案，就是不取任何数。

AC代码：（注意代码实现的时候对i做了处理，dp中的i对应A中的i-1，即dp中是个数，A中是下标。或者也可以单独处理i=0的情况，即如果i==0，j==1，t==A【0】，dp【i】【j】【t】=1，这样可能麻烦一些）

class Solution {

public:

    /**

     * @param A: An integer array

     * @param k: A positive integer (k <= length(A))

     * @param target: An integer

     * @return: An integer

     */

    int kSum(vector<int> &A, int k, int target) {

        // write your code here

    int size=A.size();

    if (target<)

    {

        return ;

    }

    vector<vector<vector<int>>> dp(size+,vector<vector<int>>(k+,vector<int>(target+,)));

    for (int i=;i<=size;i++)

    {

        for (int j=;j<=k;j++)

        {

            for (int t=;t<=target;t++)

            {

                if (j==&&t==)//前i个数中取0个和为0只有一种方案，就是不取任何数;

                {

                    dp[i][j][t]=;

                }

                else if (!(i==||j==||t==))

                {

                    dp[i][j][t]=dp[i-][j][t];

                    if (t>=A[i-])//注意是大于等于;

                    {

                        dp[i][j][t]+=dp[i-][j-][t-A[i-]];

                    }

                }

            }

        }

    }

    return dp[size][k][target];

    }

};

空间优化（滚动数组）：

可以把dp数组最外层去掉，保留两个维度。

因为 D[i][j][t] += D[i - 1][j - 1][t - A[i - 1]]（t>=A[i-1]），这个表达式说明D[i][j][t]是把上一级 i 的结果累加过来，这里我们省去了 i 这一级，在D[j][t]这个二维表里就地累加。

可以参考背包问题，背包问题dp数组优化是当前行代替上一行。这里dp是三维数组，省去一维就是当前二维表代替上一个二维表。

同理，为避免覆盖问题，j和t索引要从后向前遍历。

简单粗暴点修改上面的代码，直接去掉一个dp维度即可，AC代码如下：

class Solution {

public:

    /**

     * @param A: An integer array

     * @param k: A positive integer (k <= length(A))

     * @param target: An integer

     * @return: An integer

     */

    int kSum(vector<int> &A, int k, int target) {

        // write your code here

    int size=A.size();

    if (target<)

    {

        return ;

    }

    vector<vector<int>> dp(k+,vector<int>(target+,));

    dp[][]=;

    for (int i=;i<=size;i++)

    {

        for (int j=k;j>=;j--)

        {

            for (int t=target;t>=;t--)

            {

                if (!(i==||j==||t==))

                {

                    if (t>=A[i-])//注意是大于等于;

                    {

                        dp[j][t]+=dp[j-][t-A[i-]];

                    }

                }

            }

        }

    }

    return dp[k][target];

    }

};

代码还可以进一步优化：

int kSum2(vector<int> &A, int k, int target)

{

    int size=A.size();

    if (target<)

    {

        return ;

    }

    vector<vector<int>> dp(k+,vector<int>(target+,));

    dp[][]=;

    for (int i=;i<=size;i++)//注意此处下标范围与下面A下标对应;

    {

        for (int j=k;j>;j--)

        {

            for (int t=target;t>;t--)

            {

                if (t>=A[i-])//注意是大于等于;

                {

                    dp[j][t]+=dp[j-][t-A[i-]];

                }

            }

        }

    }

    return dp[k][target];

}

还有更简洁的版本：

class Solution {

public:

    /**

     * @param A: an integer array.

     * @param k: a positive integer (k <= length(A))

     * @param target: a integer

     * @return an integer

     */

    int kSum(vector<int> A, int k, int target) {

        // wirte your code here  T(n, k, target) = O(n*k*target). area(n, k, target) = O(k*target)

        int n = A.size();

        int dp[k+][target+];

        memset(dp, , sizeof(dp));

        dp[][] = ;

        for (int x = ; x < n; x++)

            for (int y = k; y >= ; y--)

                for (int z = target; z >= A[x]; z--)

                    dp[y][z] += dp[y-][z-A[x]];

        return dp[k][target];

    }

};

优化成二维dp后，i的遍历可以从0~size-1，也可以从1~size，并不影响结果，就是要注意与A下标对应，前者是A【i】，后者是A【i-1】。因为最初始的那张表是dp【0】【0】=1，其他位置都为0。循环开始后，数组A中每个元素都对应一个二维表，计算过程就是用当前二维表不断代替上一状态的二维表。

PS：dp数组优化前，j和t是从前向后遍历还是从后向前遍历都不影响其结果，因为计算当前i是参照i-1时的数据。

一道题做了好久……各种细节出错，不参照答案写不出来，多维动态数组对我而言还是有一定难度的，哭……

参考：

lintcode: k Sum 解题报告讲解详细，启发意义很大

LintCode-k数和讲解清晰，代码简洁

LintCode -- k数和代码很简洁

标记下我最开始的递归代码：

class Solution {

public:

    /**

     * @param A: An integer array

     * @param k: A positive integer (k <= length(A))

     * @param target: An integer

     * @return: An integer

     */

    int kSum(vector<int> &A, int k, int target) {

        // write your code here

    int result=;

    if (A.empty())

    {

        return result;

    }

    ksum(A,k,target,,,,result);

    return result;

    }

    void ksum(vector<int> &A, int k, int target,int sum,int ind,int size,int &result)

{

    if (size==k)

    {

        if (sum==target)

        {

            result++;

        }

        return ;

    }

    if (ind>=A.size())

    {

        return ;

    }

    ksum(A,k,target,sum+A[ind],ind+,size+,result);

    ksum(A,k,target,sum,ind+,size,result);

}

};

巴特西

89 k数和

描述

样例

最新文章

热门文章