leetcode 377. Combination Sum IV 组合之和 + DP动态规划 + DFS深度优先遍历

淩亂°似流年 2022-06-07 02:50 172阅读 0赞

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

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

The possible combination ways are:  
(1, 1, 1, 1)  
(1, 1, 2)  
(1, 2, 1)  
(1, 3)  
(2, 1, 1)  
(2, 2)  
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

这道题最直接的方法就是DFS深度优先遍历，但是肯定会超时。

后来网上看到了一个做法，是使用DP动态规划去处理。

建议和这一道题[leetcode 216. Combination Sum III DFS + 按照index递归遍历][leetcode 216. Combination Sum III DFS _ _index] 、[leetcode 39. Combination Sum DFS深度优先搜索][leetcode 39. Combination Sum DFS] 和这道题[leetcode 40. Combination Sum II DFS深度优先搜索][leetcode 40. Combination Sum II DFS] 当到一起学习。

同时还建议和[leetcode 322. Coin Change 类似背包问题 + 很简单的动态规划DP解决][leetcode 322. Coin Change _ _ _DP] 和 [leetcode 518. Coin Change 2 类似背包问题 + 很简单的动态规划DP解决][leetcode 518. Coin Change 2 _ _ _DP] 一起学习

还有[leetcode 474. Ones and Zeroes若干0和1组成字符串最大数量+动态规划DP+背包问题][leetcode 474. Ones and Zeroes_0_1_DP]

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    /*
     * 就想到可以用动态规划来做, 也是一个背包问题, 求出[1, target]之间每个位
     * 置有多少种排列方式, 这样将问题分化为子问题. 状态转移方程可以得到为: 
     * 
     * dp[i] = sum(dp[i - nums[j]]),  (i-nums[j] > 0);
     * */
    class Solution 
    {
        List<List<Integer>> res=new ArrayList<>();
        public int combinationSum4(int[] nums, int target) 
        {
    /*      List<Integer> one = new ArrayList<>(); 
            Arrays.sort(nums);
            getAllByDFS(nums,target,0,one);
            return res.size();*/
    
            int[] dp=new int[target+1];
            dp[0]=1;
            for(int i=1;i<=target;i++)
            {
                for(int j=0;j<nums.length;j++)
                {
                    if(i>=nums[j])
                        dp[i]=dp[i]+dp[i-nums[j]];
                }
            }
            return dp[target];
        }
    
    
        /*
         * DFS深度优先遍历
         * */
        public void getAllByDFS(int[] nums, int target, int sum,List<Integer> one) 
        {
            if(sum>target)
                return ;
            else if(sum==target)
            {
                res.add(new ArrayList<>(one));
                return ;
            }else 
            {
                for(int i=0;i<nums.length;i++)
                {
                    one.add(nums[i]);
                    getAllByDFS(nums, target, sum+nums[i], one);
                    one.remove(one.size()-1);
                }
            }
        }
    }

下面是C++的做法

这是一个很简单的DP问题，你不该做不出来的

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
    
        int combinationSum4(vector<int>& nums, int target)
        {
            vector<int> dp(1 + target, 0);
            dp[0] = 1;
            for (int i = 1; i <= target; i++)
            {
                for (int n : nums)
                {
                    if(i>=n)
                        dp[i] += dp[i - n];
                }
            }
            return dp[target];
        }
    
    
        vector<vector<int>> res;
        int combinationSum4ByDFS(vector<int>& nums, int target) 
        {
            dfs(nums, target,0,vector<int>());
            return res.size();
        }
    
        void dfs(vector<int>& a, int target, int sum,vector<int> one)
        {
            if (sum > target)
                return;
            else if (sum == target)
                res.push_back(one);
            else
            {
                for (int i = 0; i < a.size(); i++)
                {
                    one.push_back(a[i]);
                    dfs(a, target, sum + a[i], one);
                    one.pop_back();
                }
            }
        }
    };

[leetcode 216. Combination Sum III DFS _ _index]: http://blog.csdn.net/jackzhang_123/article/details/78059803
[leetcode 39. Combination Sum DFS]: http://blog.csdn.net/jackzhang_123/article/details/77802950
[leetcode 40. Combination Sum II DFS]: http://blog.csdn.net/jackzhang_123/article/details/77803003
[leetcode 322. Coin Change _ _ _DP]: http://blog.csdn.net/jackzhang_123/article/details/78150520
[leetcode 518. Coin Change 2 _ _ _DP]: http://blog.csdn.net/JackZhang_123/article/details/78820585
[leetcode 474. Ones and Zeroes_0_1_DP]: http://blog.csdn.net/JackZhang_123/article/details/78781584