子集合问题,这两个算法有什么区别?

mitcc
  • 68

普通的子集和问题:给定一个已经排序且无重复的数组,以及一个目标值,输出子集合为目标值的个数,例如:

nums = [1, 2, 3]
target = 4

满足条件的子集为:

(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

则输出结果为:7

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; ++i) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }

上面的代码是正确的算法,这是 LeetCode 上最近的一道题,跟找零钱算法(给定一个数组,即币种面值的集合,返回一个目标值可以有多少种零钱组合)很类似,对于找零钱算法,上面的(1, 1, 2)(1, 2, 1)(2, 1, 1) 只能计算一次,(1, 3)(3, 1) 也只能计算一次,结果为 4

找零钱算法是这样子的:

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int i = num; i <= target; ++i) {
                dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }

找零钱算法就是对子集合算法的结果去重得到的,代码上的差别仅仅是内外两重循环的顺序变了,这个我就不太理解,为什么循环顺序变了,会导致一个结果含重复序列,另一个不含?换言之,找零钱算法相比较子集合算法,是如何避免重复的呢?

回复
阅读 4.8k
1 个回答
✓ 已被采纳

谢邀,非常好的问题!

DP 从来都是很抽象的,希望我能说清楚。

仔细品味两种方法,你会发现:第二种被非常隐晦地人为地加上了一种“序”

假设同时有个三维数组 result[target][i][j],用于储存所有可能的结果集:result[target][i] 为一个数组,存储的是 和为 target 的第 i 种可能子集 。处理 dp[i] 时,假想同时有个 将 result[i - num] 下所有序列拷贝到 result[i] 下,同时往所有 result[i][index] 的最后面添加一个 num 的操作。这样结果集就会同步生成。

在第一种算法中,计算 某个 result[i] 时,我们需要用到 result[i - num],而由于循环 num: nums 在内层,result[i - num] 中有可能出现 在 nums 中 比 num 要靠后的项

而在第二种算法中,由于循环 num: nums 在外层,使用 result[i - num] 时,其储存的结果集包含的元素只可能来自于 nums 中排在 num 前面的元素(因为后面的还没遍历到)。换句话说:如果将 result 打印出来,那么每个结果集的元素排列必定是按照原先在 nums 中的顺序。既然有了顺序,那么自然不会计算重复项了。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏