代码随想录Leetcode377. 组合总和 Ⅳ
题目:
代码(首刷看解析 2024年2月27日):
class Solution {
public:
// 思路:动态规划
int combinationSum4(vector<int>& nums, int target) {
// 1条件判断:无
// 2定义dp 初始化 总和为target的数量
vector<int> dp(target + 1, 0);
dp[0] = 1;//虚拟,实际dp[0] = 0
// 3遍历 TODO:先target,再nums(不同顺序)
for (int j = 0; j <= target; ++j) {
for (int i = 0; i < nums.size(); ++i) {
if (j - nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]])
dp[j] += dp[j - nums[i]];
}
}
// 4递推公式:
return dp[target];
}
};
原文地址:https://blog.csdn.net/qq_52313711/article/details/136319037
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!