leetcode 377 组合总和Ⅳ

傷城~ 2022-09-17 01:55 19阅读 0赞

## 前言 ##

题目：[377. 组合总和 Ⅳ][377. _]

参考题解：[组合总和Ⅳ-代码随想录][-]

--------------------

## 提交代码 ##

### 动态规划 ###

01背包问题，动态规划问题。可以使用回溯暴力解决。回溯时，下标不断向前。

(组合)完全背包问题，动态规划问题。可以使用回溯解决。回溯时，下标从头开始。

(排列)完全背包问题，使用回溯暴力解决。尽然，也可以使用动态规划解决，下面我们仔细看下。

[01背包问题-二维数组解决][01_-]

**先遍历物品，还是先遍历背包，都可**。因为递推公式，它依赖的是正上方和左上方的元素。

// weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    
        }
    }
    
    // weight数组的大小 就是物品个数
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        for(int i = 1; i < weight.size(); i++) { // 遍历物品
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }

[01背包问题-滚动数组解决][01_- 1]

**需要先遍历物品，后遍历背包，并且背包的容量要从大到小遍历**。背包容量从大到小遍历：因为递推公式需要正上方和左边的数字。而这些数字来源于上次循环的迭代保留。如果背包容量从小到大遍历：同一个物品，会尽量尝试，如果再放入一个value\[i\]替换其中的部分内容，能否得到更大值。如果先遍历背包，再遍历物品，而背包容量是从大到小遍历，dp\[target\]我们需要的值，仅会放入一个物品。

for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    
        }
    }

[(组合)完全背包-滚动数组解决][- 1]

**先遍历物品，再遍历背包。背包的容量要从小到大**。比如，先遍历物品，再遍历背包，背包容量从小到大，则dp\[j\]在不断变大的过程中，会不断尝试，能否使用当前元素(的一个)，替换其中的部分内容，以获得更大的值。

[(排列)完全背包-滚动数组解决][-]

**先遍历背包，再遍历物品。背包的容量要从小到大**。背包容量从小到大，可以装入相同的元素。先遍历背包，后遍历物品。这样，加入target，先1后5，先5后1均可存在。

for(int j=0; j<=target; j++){ // 先遍历背包
        for(int i=0; i<nums.size(); i++){ // 后遍历物品
            if(j>=nums[i]){
                dp[j] += dp[j-nums[i]]; // 当背包容量为j时候=前面dp[j-nums[i]]的组合+物品i
            }
        }
    }

无聊的背包问题。我这个高数基本都忘光的人，这种思维难度而非工程难度，不想搞。

下面是本题的提交代码。

class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target) {
            // 思路：完全背包中的排列问题
            // 先遍历背包，再遍历物品。(6-1=5;6-5=1)
    
            // dp[j]：背包容量为j时，组合数
            vector<int> dp(target+1,0);
            dp[0] = 1; // 初始化，表示仅使用某一个物品，可以装满
            for(int j=0; j<=target; j++){ // 先遍历背包
                for(int i=0; i<nums.size(); i++){ // 后遍历物品
                    if(j>=nums[i]){
                    // if (j>=nums[i] && dp[j] < INT_MAX - dp[j - nums[i]]) { // 这题目怕不是智障？题目已经限定结果不会溢出；但是通过丢弃正确解来避免溢出，也是绝了
                        dp[j] += dp[j-nums[i]]; // 当背包容量为j时候=前面dp[j-nums[i]]的组合+物品i
                    }
                }
            }
    
            return dp[target];
        }
    };

### 回溯-超时 ###

组合/排列问题，使用回溯方法进行暴力破解。思路必然没问题，但是会超时。下面是回溯代码实现。

#include <vector>
    #include <algorithm>
    #include <iostream>
    
    using namespace std;
    
    class Solution {
    public:
        void backTracking(const vector<int>& nums, const int& target, int& sum, int& cnt){
            if(sum==target){
                cnt++;
                return;
            }
    
            for(int i=0; i<nums.size() && sum+nums[i]<=target; i++){
                // 同一层不可以出现相同的元素；这个判断没必要，题目已经限定为不同元素
                if(i>0 && nums[i]==nums[i-1])
                    continue;
                sum += nums[i];
                backTracking(nums,target,sum,cnt);
                sum -= nums[i];
            }
        }
    
        int combinationSum4(vector<int>& nums, int target) {
            sort(nums.begin(),nums.end());
            int cnt = 0;
            int sum = 0;
            backTracking(nums,target,sum,cnt);
            return cnt;
        }
    };
    
    int main(void){
        vector<int> nums = {1,2,3};
        // int target = 4;
        int target = 32; //结果为181997601
        Solution s;
        cout<<s.combinationSum4(nums,target)<<endl;
    }

[377. _]: https://leetcode-cn.com/problems/combination-sum-iv/
[-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.md
[01_-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.md
[01_- 1]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.md
[- 1]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.md