377组合总和 Ⅳ

题目

给你一个由 不同 整数组成的数组 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[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000

分析

该题可以抽象为完全背包问题，需要注意的是，本题要求的是排列数，动规五部曲如下：

1、确定dp数组下标及含义：dp[j]为当背包容量为i时有多少种排列组合
2、确定递推公式：dp[j] += dp[j-nums[i]]
3、初始化dp数组：dp[0] = 1，为了满足递推公式
4、确定遍历顺序：因为求的是排列数，所以要先背包后物品，并从左向又遍历以下为图解，先物品后背包时，物品只按一个顺序放置，即1，2，5，先背包后物品时，不断循环物品，则会出现不一样的序列，如果用的二维数组的话，先背包还是先物品就无所谓了
5、打印dp数组：如果有错误或者不理解可以打印dp数组
在这里插入图片描述

题解

题解一：

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> 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[i-num]<INT_MAX - dp[i]){
                    dp[j] += dp[j-nums[i]];
                }
            }
        }
        return dp[target];
    }
};

注：dp[j] += dp[j-nums[i]]会出现超出整数范围的情况，所以用减法检查一下dp的范围，即dp[i-num]<INT_MAX - dp[i]。
题解二：

#include<iostream> 
#include<vector>
using namespace std;

int test(vector<int>& nums, int target) {
    vector<int> 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-nums[i]]<INT_MAX - dp[j]){
                dp[j] += dp[j-nums[i]];
            }
        }
    }
    return dp[target];
}
int main(){ 
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i = 0;i<n;++i){
    	cin>>nums[i];
	}
	int target;
	cin>>target;
	cout<<test(nums,target)<<endl;
    return 0;
}