377号组合数问题

Question

老师您好！377号问题是求从数组中挑选一些数组成特定和的组合数，我不理解为什么把完全背包问题中的目标数放在外循环，数组中数放在内循环求出的就是包含重复的结果，可以给我解释一下么？

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n=nums.size();
        if(n==0)
            return 0;
        
        vector<int> memo(target+1,0);
        memo[0]=1;
        for(int i=1;i<=target;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(nums[j]<=i)
                    memo[i]=memo[i]+memo[i-nums[j]];
            }
        }
        return memo[target];
    }
};

Answer 1

liuyubobobo 2018-02-28 17:11:56

如果数组中的数字放在外循环，相当于：已知用nums[0...i]这些数字凑成[0...target]的方法数，现在需要新考虑一个数字nums[i+1]，现在，凑成[0...target]的方法有多少？此时，新考虑的这个nums[i+1]摆在哪里变成了问题。以凑成j为例，由于之前凑成j的方法完全没有用这个nums[i+1]，所以nums[i+1]可以摆放在原先凑成j的所有方法的所有数字之间！（这还不考虑需要多个nums[i+1]的情况）。所以，所以，仅仅记住原先用nums[0...i]这些数字凑成j的方法数量是不够的，还需要具体是怎么凑出来的，才能找到摆放新的nums[i+1]的所有方法。

但是把目标数放在外循环，相当于每次需要考虑：用所有的nums数字凑成[0...j]的方法数已经知道了，现在要凑成j+1，多了几种方法？这时，用所有的nums凑成[0...j]的数量中，已经包含了不同顺序的结果，我们只需要考虑，在现有的所有凑成的方法后面，添加nums[0], nums[1], nums[2]，... 能不能凑成j+1就好了。

这么说可能还是比较抽象。如果觉得自己理解的还不够透彻，我建议你用377号题目的例子：nums = [1, 2, 3]，target = 4，走一遍上面的程序。i从1到4；j从0到2，一共循环才执行12次。每次更新memo[i]的时候，如果memo[i]变大了的话，都自己写出当前的memo[i]所记录的凑成数字i的方法数都是那几种（一共才7种），一定可以帮助你更深刻的理解这个问题。不要嫌麻烦！跟踪经典算法实现中的变量是如何变化的，想明白为什么会这么变化，和自己哪里理解的不一样，或者自己之前的理解漏掉了什么，是深入理解算法的非常有效的方法：）

如果在这个基础上，能够自己尝试换个方法编写，就更好了。比如自己实际思考一下，如果两层循环的顺序变了，在实现逻辑上到底有什么差别？有什么改变？多做这样的思考和实验，代码水平想不提高都难：）

加油！

• 提问者 河水洗回忆 #1

  谢谢老师百忙之中帮我解决这个问题！现在我已经明白了，谢谢老师！

• ShiveryMoon #2

  我列了整整一张A4纸，发现这个循环的逻辑实在是太巧秒了。。。
  
  按这个例子来说，其实memo[4]=memo[3]+memo[2]+memo[1]
  
  每次更新memo[i]的时候，其实就是把num[j]添加到memo[i-j]的所有情况(列表)的末尾，而memo[i-j]本身代表的int值是不变的。
  
  想不到这么简单的几行代码的内在逻辑这么复杂

• liuyubobobo 回复 ShiveryMoon #3

  大赞！

点开查看后面2条评论

Answer 2

ShiveryMoon 2018-03-03 13:43:35

我正好也想问这个问题来着，内外层循环反过来居然就能从求组合变成求排列，我都傻了