Lintcode 89 K sum

K Sum

题目描述

给定一个输入数组 array(每个数不同),还有两个整数 k 和 target,在数组 array 中找出 k 个元素,使得这 k 个元素相加等于 target,问有多少种组合方式,输出组合方式的个数。

注:在一种组合方式中,一个元素不能够被重复选择

这里就说明了要用01背包的思路,内层从大到小循环

题目分析

我们之前讲过 Two Sum,也提到过 3 Sum,还有 4 Sum,那这道题是否可以套用之前的解法呢?

这里有一个细节不知道你是否发现,就是 这道题目仅仅是让你输出所有组合方式的个数,并没有让你输出所有的组合方式,这是决定是否使用动态规划很重要的一点。

如果没有这个 k,我相信你会很直接地想到使用 01 背包问题 的解法,那我们可以思考一下,基于原来的解法,如果增加了 k 这个限制,我们需要额外做些什么事情呢?

因为 k 会决定问题的状态,因此我们的状态数组中也要考虑 k,在考虑将第 k 个元素放入背包中,我们需要看的是背包中存放 k – 1 个元素的情况,这么看来,其实相比普通的 01 背包问题,这道题目仅仅是增加了一维状态,没有其他的变化。

参考代码

public int kSum(int[] array, int k, int target) {
    int[][] dp = new int[target + 1][k + 1];

    dp[0][0] = 1;

    for (int i = 0; i < array.length; ++i) {
        for (int j = target; j >= array[i]; --j) {
            // 和普通 01背包问题 相比,仅仅是多了一层状态需要考虑
            // 这层状态记录的是背包里面元素的个数
            // 我们放入第 r 个元素的时候,必须确保背包里面已经有 r - 1 个元素
            for (int r = 1; r <= k; ++r) {
                dp[j][r] += dp[j - array[i]][r - 1];
            }
        }
    }

    return dp[target][k];
}

 

for (int r = 1; r <= k; ++r) {
                dp[j][r] += dp[j - array[i]][r - 1];

这一部分代码的理解
可以把dp的每一行的和当成原来普通背包问题更新的那个数

上一篇:three.js学习笔记(五)——Shadows阴影


下一篇:【LeetCode/LintCode】 题解丨微软面试题:大楼轮廓