leetcode 377. 组合总和 Ⅳ

2023.8.17

 

         本题属于完全背包问题，乍一看和昨天那题 零钱兑换II 类似，但细看题目发现：今天这题是排列问题，而“零钱兑换II”是组合问题。排列问题强调顺序，而组合顺序不强调顺序。

        这里先说个结论：先遍历物品，再遍历背包，求出来的是组合数。(即{1，2}和{2，1}是等价的)       而先遍历背包，再遍历物品，求出来的是排列数。(即{1，2}和{2，1}是不等价的。)

        本题思路还是和昨天那题类似，但是物品和背包的遍历顺序需要调换一下，因为本题需要求的是排列数。 代码如下：

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<unsigned int> dp(target+1);dp[0] = 1;for(int j=0; j<=target; j++){for(int i=0; i<nums.size(); i++){if(j >= nums[i]){dp[j] += dp[j-nums[i]];}}}return dp[target];}
};

        ps：cpp代码的dp数组需要声明为<unsigned int>，不然如下示例通过不了。