LeetCode 377 组合总和Ⅳ

377.组合总和 Ⅳ

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

此处 nums 中的元素可以使用无限次。

示例：

输入：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)
请注意，顺序不同的序列被视作不同的组合。

动态规划

此处就是一个完全背包问题，但是背包的最优化问题是最多的方案数。并且在题中指出了，顺序不同的序列将会被视为不同的组合，也就是此处元素的选择上是有序的。那么采取滚动数组的方式来实现，需要先遍历背包，再遍历元素，因为只有这样才能保证选取上的有序。

1. 动态规划数组的定义：定义数组 dp[target+1] 表示总和为 target 的元素选择方案个数。

2. 动态规划数组的推导：在 j 次迭代中，从元素 0-n 中进行选择，那么相较于前面的方案，主要是背包容量增大。那么 dp[j]=dp[j]+dp[j-nums[i]]

3. 动态规划数组的初始化：在初始时，装满 dp[0] 的方案有一种，那么 dp[0]=1

4. 动态规划数组的遍历顺序：此处是先遍历背包再遍历物品，那么先从前向后遍历背包再从前向后遍历物品。

5. 举例验证：对于 nums={1,2,3} , target=4 动态规划的过程为:

dp={1,0,0,0,0}
dp={1,1,0,0,0}
dp={1,1,2,0,0}
dp={1,1,2,4,0}
dp={1,1,2,4,7}

代码实现：

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<long long> dp(target+1,0);
        dp[0]=1;
        for(int j=1;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];
    }
};

对于本题的测试用例，LeetCode官方给定的测试用例存在一定问题，会有整数溢出的问题，因此需要加上： dp[j]<INT_MAX-dp[j-nums[i]]