今日重要总结一下动态规划完全背包的一道标题，377. 组合总和 Ⅳ
标题：377. 组合总和 Ⅳ
Leetcode标题地点
标题描述：
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
标题数据包管答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
表明：
所有大概的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，次序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3
输出：0
提示：
1 <= nums.length <= 200
1 <= nums <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000
本题重难点
这是一道典型的背包题目，本题给定的数组内里的元素可以重复取，以是这是一个完全背包。
本题标题描述说是求组合，但又说是可以元素相同次序不同的组合算两个组合，其实就是求排列！
弄清什么是组合，什么是排列很重要。
组合不夸大次序，(1,5)和(5,1)是同一个组合。
排列夸大次序，(1,5)和(5,1)是两个不同的排列。
但其本质是本题求的是排列总和，而且仅仅是求排列总和的个数，并不是把所有的排列都列出来。
假如本题要把排列都列出来的话，只能使用回溯算法爆搜。
动规五部曲分析如下：
- 确定dp数组以及下标的寄义
dp: 凑成目标正整数为i的排列个数为dp
- 确定递推公式
dp（考虑nums[j]）可以由 dp[i - nums[j]]（不考虑nums[j]） 推导出来。
由于只要得到nums[j]，排列个数dp[i - nums[j]]，就是dp的一部分。
在一文搞懂0 - 1背包之494. 目标和题目和 一文搞懂完全背包之518. 零钱兑换 II题目中我们已经讲过了，求装满背包有几种方法，递推公式一般都是dp += dp[i - nums[j]];
本题也一样。
- dp数组如何初始化
由于递推公式dp += dp[i - nums[j]]的缘故，dp[0]要初始化为1，这样递归其他dp的时候才会有数值基础。
至于dp[0] = 1 有没有意义呢？
其实没有意义，以是我也不去强行表明它的意义了，由于标题中也说了：给定目标值是正整数！ 以是dp[0] = 1是没有意义的，仅仅是为了推导递推公式。
至于非0下标的dp应该初始为多少呢？
初始化为0，这样才不会影响dp累加所有的dp[i - nums[j]]。
- 确定遍历次序
个数可以不限使用，说明这是一个完全背包。
得到的聚集是排列，说明需要考虑元素之间的次序。
本题要求的是排列，那么这个for循环嵌套的次序可以有说法了。
在一文搞懂完全背包之518. 零钱兑换 II题目中就已经讲过了。
假如求组合数就是外层for循环遍历物品，内层for遍历背包。
假如求排列数就是外层for遍历背包，内层for循环遍历物品。
假如把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的聚集，不会有{3,1}这样的聚集，由于nums遍历放在外层，3只能出如今1后面！
以是本题遍历次序最终遍历次序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。
- 举例来推导dp数组
我们再来用示例中的例子推导一下： 在这里插入图片描述：
C++代码
- class Solution {
- public:
- int combinationSum4(vector<int>& nums, int target) {
- vector<int>dp(target + 1, 0);
- dp[0] = 1;
- for(int i = 0; i <= target; i++){
- for(int j = 0; j < nums.size(); j++){
- if(i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]] ){
- dp[i] += dp[i - nums[j]];
- }
- }
- }
- return dp[target];
- }
- };
dp < INT_MAX - dp[i - num]。
总结
动态规划
英文：Dynamic Programming，简称DP，假如某一题目有很多重叠子题目，使用动态规划是最有用的。
动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪婪，贪婪没有状态推导，而是从局部直接选最优的
对于动态规划题目，可以拆解为如下五步曲，这五步都搞清晰了，才能说把动态规划真的掌握了！
- 确定dp数组（dp table）以及下标的寄义
- 确定递推公式
- dp数组如何初始化
- 确定遍历次序
- 举例推导dp数组
这篇文章重要总结了一些动态规划办理518. 零钱兑换 II题目，依然是使用动规五部曲，做每道动态规划标题这五步都要弄清晰才能更清晰的明白标题！
求装满背包有几种方法，递归公式都是一样的，没有什么差别，我们在一文搞懂0 - 1背包之494. 目标和题目中就已经讲过了
- dp[j] += dp[j - nums[i]];
在求装满背包有几种方案的时候，认清遍历次序是非常关键的。
- 假如求组合数就是外层for循环遍历物品，内层for遍历背包。（也就是0-1背包一维dp数组常用写法）
- 假如求排列数就是外层for遍历背包，内层for循环遍历物品。
本题与一文搞懂完全背包之518. 零钱兑换 II题目就是一个鲜明的对比，一个是求排列，一个是求组合，遍历次序完全不同。
欢迎各人关注本人公众号：编程复盘与思索随笔
(关注后可以免费获得本人在csdn发布的资源源码)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
