问题
给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum-iv
思路
完全背包的方案数问题,装满,考虑顺序
for循环交换顺序即可
完全背包
代码
class Solution { public: int combinationSum4(vector& nums, int target) { // 完全背包的方案数问题,这个考虑顺序,for循环顺序 int n=nums.size(); vector dp(target+1,0); dp[0]=1; for(int j=0;j<=target;j++) // 完全背包正序 for(int i=1;i<=n;i++){ if(j>=nums[i-1]) dp[j]+=dp[j-nums[i-1]]; } return dp[target]; } };
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)