动态规划 Leetcode 377 组合总和IV
组合总和IV
Leetcode 377
学习记录自代码随想录
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {// 1.dp[j]表示背包容量为j时的所有组合数目vector<long unsigned int> dp(target+1, 0);// 2.递推公式：dp[j] += dp[j-nums[i]]// 3.dp数组初始化；dp[0] = 1;// 4.遍历顺序因为组合数和顺序有关，所以先遍历背包，再遍历物品for(int j = 0; j < target+1; j++){for(int i = 0; i < nums.size(); i++){if(j >= nums[i]) dp[j] += dp[j-nums[i]];}}return dp[target];}
};