排序的数目
题目
给定一个由 不同 正整数组成的数组 nums ,和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排列中出现任意次,但是顺序不同的序列被视作不同的组合。
题目数据保证答案符合 32 位整数范围。
链接
无效DFS
DFS不剪枝的情况下,没有办法在有限时间内结束相应的任务
class Solution {
public:
int ans=0;
int n;
void dfs(int sum,vector<int>&nums,int & target){
if(sum>target){
return;
}else if(sum==target){
ans++;
}
for(int i=0;i<n;i++){
dfs(sum+nums[i],nums,target);
}
}
int combinationSum4(vector<int>& nums, int target) {
n=nums.size();
for(int i=0;i<n;i++){
dfs(nums[i],nums,target);
}
return ans;
}
};
题解
思路:动态规划
初始化 dp[0]=1
遍历 j 从 1 到target,对于每个 j,进行如下操作:
遍历数组 nums 中的每个元素 num,当 num≤j 时,将 dp[j−num] 的值加到 dp[j]。
最终得到 dp[target]
dp[target] 的值即为答案
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
int n=nums.size();
vector<int>dp(target+1,0);
dp[0]=1;//和为0只有一种方式
for(int j=1;j<=target;j++){
for(auto num:nums){
if(j>=num&&dp[j-num]<INT_MAX-dp[j]){//c++需要注意int溢出的问题,所以要添加dp[j-num]<INT_MAX-dp[j]作为判断条件
dp[j]+=dp[j-num];
}
}
}
return dp[target];
}
};
标签:专项,target,nums,int,sum,num,dp,Leetcode,DP
From: https://www.cnblogs.com/SaltyCheese/p/17280730.html