leetcode 377. Combination Sum IV | 377. 组合总和 Ⅳ（动态规划）

喜欢ヅ旅行 2022-08-29 12:56 97阅读 0赞

## 题目 ##

[https://leetcode.com/problems/combination-sum-iv/][https_leetcode.com_problems_combination-sum-iv]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

最近养成了上来直奔 Related Topics 的习惯…  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

确认过眼神，又是个 dp 问题！  
这样算下来，这是全局第 4 道没看答案自己想出来的 dp 问题了…  
让 dp 不再成为玄学，真的指日可待了吗…

##### 思路 #####

又是个拆数问题，明显可以划分为子问题。而且题目中说了，不同的排列顺序将被看做是不一样的结果，所以 target = 加数1 + 加数2，我们根据 nums 分别固定加数1，剩余的加数2直接从 dp 数组中取以及计算好的状态，就可以保证结果不重复。

先用前几个数模拟，草稿如下。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]  
上代码：

class Solution { 
        public int combinationSum4(int[] nums, int target) { 
            Arrays.sort(nums);
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for (int i = 1; i <= target; i++) { 
                int sum = 0;
                for (int n : nums) { 
                    if (i - n < 0) break; // 要先sort，保证后面都<0才能break
                    sum += dp[i - n];
                }
                dp[i] = sum;
            }
            return dp[target];
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_combination-sum-iv]: https://leetcode.com/problems/combination-sum-iv/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/d96b2943b080425ca817df59eafd256b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/85e93ba24ac947a59d4250fa3727cbf0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20220829/8ec6b3078429462a9f78ddf1d6abf575.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/da960a3add2543aa98c583521cee4009.png