leetcode 377

Question

//动态规划
    //时间复杂度O(n*target)
    //空间复杂度O(n*target)
    //状态是考虑放入第i个数字
    //由此状态转移方程为f(i,target)=f(i-1,target)+f(i-1,target-nums[i])+f(i,target-nums[i])
    public int DongCombinationSum4(int[] nums, int target) {
        int n=nums.length;
        if(n==0||target<0){
            return 0;
        }//如果没有数字或者目标数字小于0，返回0就可以了
        int[][]memo=new int[n][target+1];//表示范围[0,index]的数字组成target的所有的方案
        for(int j=0;j<=target;j++){
            if(j%nums[0]==0){
                memo[0][j]=1;
            }else{
                memo[0][j]=0;
            }
        }
       for(int i=1;i<n;i++){
           for(int j=0;j<=target;j++){
               if(j>=nums[i]){
                   memo[i][j]=memo[i-1][j]+memo[i-1][j-nums[i]]+memo[i][j-nums[i]];
                   /*
                   这里我认为的是和完全背包问题是一样的，就是对于[0-i]的目标为j，组成它的情况
                   就是要么不取第i个数字，那就是对于[0,i-1]目标为j的情况，以及要么取第i个数字
                   那就是对于[0,i-1]目标为j-nums[i]的情况，还有一种就是对于[0,i]，目标为j-nums[i]
                   的情况，这三种情况的和就是最后的结果，但是答案和预想的不一样
                    */
               }else{
                   memo[i][j]=memo[i-1][j];
               }
           }
       }
       return memo[n-1][target];
    }

老师麻烦看一下，我这个问题的思路出错在哪里了？

Answer 1

liuyubobobo 2019-07-25 03:29:34

和背包问题不一样。最大的区别是，背包问题你是没有顺序的。你只要让背包价值最大就好了。按照什么顺序放物品不重要。

而这个问题，恰恰让你记的顺序，就是和放物品的顺序相关的。

我的参考代码如下：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0377-Combination-Sum-IV/cpp-0377/main2.cpp

主体逻辑是这样的：

memo[0] = 1;
for(int i = 1; i <= target; i++)
    // 对于每一个新的目标i，都看一遍nums[0...n-1]所有数字
    for(int j = 0; j < n; j ++)
        if(nums[j] <= i)
            // 用当前的nums[j] 加上能凑成 i - nums[j] 的方法数
            memo[i] += memo[i - nums[j]];

另外，这个问题的结果可能整形溢出，在这种情况下返回-1就可以AC。题目中对此似乎没有注明。我不确定是不是C++特有的问题。所以上面的参考代码链接你会看到循环内对整形溢出的判断。单位了说明逻辑，上的代码不包含。

再仔细体会一下？：）

继续加油！：）

• 提问者 pfco #1

  非常感谢！

• 讲武德的年轻人 #2

  我也要请教bobo老师，怎么理解背包问题没有顺序，而377这个题目有顺序？我的理解是，背包问题也是有顺序吧？毕竟当前放入item的大小和价值会影响后面放入的东西大小和价值。我看到一篇文章关于DP背包问题的总结，文中说，如果需要考虑元素顺序，那么外层循环就需要遍历状态（比如377中的target），内层循环则遍历元素；如果不需要考虑元素顺序，如0-1背包问题，则外层循环就要遍历元素，而内层循环遍历状态。我刚学习dp，好有点模糊，请老师点拨。谢谢！

• liuyubobobo 回复 讲武德的年轻人 #3

  我说的是对**结果**要不要求顺序。在过程中，任何问题肯定有处理的顺序。但对于背包问题，只要求放入哪些物品，让最终背包价值最大即可；先放入 1 后放入 2，还是先放入 2 后放入 1，是一样的。而对于这个问题，[1, 2] 和 [2, 1] 是两个答案。
  
  至于你说的总结，不要背这种东西，什么如果问题是这样，就要这样做；问题是那那样，就要那样做。我从来不懂这种东西，处理问题也从来不依赖于这种总结。所以很抱歉，你后面说的那段话，我根本就没去看，也没去想到底对不对。因为他真的没用。问题可以有无数种变形，靠这种总结即不可靠，你也不能真正的掌握。能快速解决问题的人，不是因为心中记住了一万种这类总结。
  
  请只是从问题出发，去看问题具体是什么，所以逻辑是怎样的。如果你认为那样也可以，就实际尝试一下，看看是不是真的可以。如果发现有问题，去实际使用一个小的测试用例跟踪一下，看看为什么不可以。去看你最初为什么认为可以？但实际却不可以？自己哪里想错了？同样的代码（或者思路）为什么可以解决那个问题，却不可以解决这个问题？这两个问题的区别到底是什么？导致了逻辑和代码到底有了什么区别？请用这种方式去加深理解问题和处理问题的逻辑之间的关系和异同。
  
  继续加油！：）

Answer 2

提问者 pfco 2019-07-24 21:33:52

老师，我认为这个问题我是忽略了顺序性这个东西，但是确实不知道应该怎么改，逻辑上感觉没什么问题