LeetCode 377.组合总和IV 可解决一步爬m个台阶到n阶楼顶问题（ 完全背包 + 排列数）

给你一个由 不同 整数组成的数组 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）区分组合和排列：

组合：不强调顺序，(1,5) 和 (5,1)是同一个组合

排列：是强调顺序，(1,5) 和 (5,1)是两个不同的排列

可知本题的本质求的是排列总和，且仅仅求的是排列总和的个数，并不是把所有的排列都列出来~

若本题需要把排列都列出来的话，只能用回溯算法暴搜！

>>动规五部曲分析如下：

1.确定dp数组以及下标的含义

        dp[j] : 凑成目标正整数为 j 的排列个数为 dp[j]

2.确定递归公式

        dp[j] （考虑nums[i]）可以由dp[j - nums[i]] (不考虑nums[i]） 推导出来

因为只要得到 nums[i],排列个数 dp[j - nums[i]]，就是dp[i]的一部分

在动态规划：494.目标和 和 动态规划：518.零钱兑换II 中我们已经讲过了，求装满背包有几种方法，递推公式一般都是 dp[j] += dp[j-nums[i]]; 本题一样！

3.dp数组初始化

因为 dp[j] += dp[j - nums[i]] ，所以dp[0]要初始化为1，这样递归其他dp[j]的时候才会有数值基础

dp[0] = 1;其实是没有意义的，因为题目中说了，给定的目标值是正整数，所以dp[0] = 1是没有意义的，仅仅是为了推导递推公式。

非0下标的dp[j] 应该初始为0，这样才不会影响dp[j] 累加所有的 dp[j - nums[i]];

4.确定遍历顺序

个数是可以不限制使用的，所以本题可以使用完全背包来解决，得到的集合是排列，说明需要考虑元素之间的顺序。因为本题要求的是排列，那么需要格外注意for循环嵌套的顺序~

在动态规划：518 零钱兑换II 中讲到：

• 如果求组合数就是外层 for 循环遍历物品，内层for循环遍历背包
• 如果求排列数就是外层 for 循环遍历背包，内层for循环遍历物品

举个例子：计算dp[4]时，结果集想要有{1,3},{3,1}这两个集合，那么得先遍历背包，再遍历物品，才可以；反之则结果集只有{1,3}这样的集合。

因此可以确定本题遍历顺序最终的遍历顺序为：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前向后遍历（完全背包）

5.举例来推导dp数组

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {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] && dp[j] < INT_MAX - dp[j - nums[i]])dp[j] += dp[j-nums[i]];}}return dp[target];}
};// [0-i] 装满背包为j 有dp[j]种
// dp[j] += dp[j-nums[i]]

• 时间复杂度：O(target * n)，其中 n 为nums的长度
• 空间复杂度：O(target)

C++测试用例有两个数相加超过int的数据，所以需要在 if 里加上dp[j] < INT_MAX - dp[j - nums[i]]

参考和推荐文章、视频：

代码随想录 (programmercarl.com)

动态规划之完全背包，装满背包有几种方法？求排列数？| LeetCode：377.组合总和IV_哔哩哔哩_bilibili

往期文章：

完全背包 动态规划 + 一维dp数组

LeetCode 518.零钱兑换II 动态规划 + 完全背包 + 组合数

【总结】

• 求装满背包有几种方法，递归公示都是一样的，没有差别，但关键在于遍历顺序！
• 本题与动态规划：518.零钱兑换II 的区别，一个是求排列数，一个是求组合数，遍历顺序完全不同。

来自代码随想录的课堂截图！ 

爬楼梯拓展成一步可以爬m个台阶，这个代码怎么写？思路是怎么样的？

leetCode 70.爬楼梯 动态规划_呵呵哒(￣▽￣)"的博客-CSDN博客

好问题：若一步一个台阶，两个台阶，三个台阶，直到 m 个台阶，有多少种方法爬到n阶楼顶。一步可以爬几个台阶，其实就是相当于每个物品，有多少种不同的方法可以爬到楼顶，相当于装满这个背包有多少种方法。比如：如果说我们先爬了一步再爬两步，再爬一步可到楼顶。和我们先爬一步，再爬一步，后爬了两步到了楼顶。请问这是几种爬楼梯的方法？很明显，这是两种方法，所以说爬楼梯的话，我们求的这个集合的个数，我们要强调元素的顺序，所以说和本题（leetCode 377.组合总和IV）是一样的。同样是强调元素之间的顺序的，也就是说 {1,2,1} 和 {1,1,2} 这是两个集合,要分别来计数。

class Solution {
public:int climbStairs(int n) {vector<int> dp(n + 1,0);dp[0] = 1;int m = 2;// m 表示一步最多可以爬多少个台阶for(int j = 1;j <= n; j++) { // 背包for(int i = 1;i <= m; i++) { // 物品if(j >= i)dp[j] += dp[j-i];}}return dp[n];}
};

代码中m表示最多可以爬m个台阶，代码中把m改成2就是本题70.爬楼梯可以AC的代码了。