【代码随想录】刷题笔记Day45
2024-01-07 18:20:43
前言
- 早上又赖了会床......早睡早起是奢望了现在,新一年不能这样!支棱起来!
377. 组合总和 Ⅳ - 力扣(LeetCode)
- 这一题用的就是完全背包排列数的遍历顺序:先背包再物品,从前往后
- 求的也是有几种方法,dp[j] += dp[j - nums[i]];? dp[0] = 1
- 测试用例有坑,dp[j]求和不能超过32位整数范围......
-
class Solution { public: int combinationSum4(vector<int>& nums, int target) { vector<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] < INT_MAX - dp[j - nums[i]]) // 如果求和大于INT_MAX就不求了 dp[j] += dp[j - nums[i]]; } } return dp[target]; } };
322. 零钱兑换 - 力扣(LeetCode)?
- dp[j]:凑足总额为j所需钱币的最少个数为dp[j]
- 递推公式:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
- 初始化:dp[0] = 0;? 其他为INT_MAX
- 遍历顺序,求最小个数,排列/组合无影响,先物品还是先背包都行
- 没凑满就用是否是初始值判断,dp[j - coins[i]] 更新过了说明可以凑满
-
class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; for (int i = 0; i < coins.size(); i++) { // 遍历物品 for (int j = coins[i]; j <= amount; j++) { // 遍历背包 if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值,没凑满,跳过 dp[j] = min(dp[j - coins[i]] + 1, dp[j]); } } } if (dp[amount] == INT_MAX) return -1; return dp[amount]; } };
?279. 完全平方数 - 力扣(LeetCode)
- ?完全平方数就是硬币,总和n就是背包,求最小值,和上一题类似
-
// 先背包后物品 class Solution { public: int numSquares(int n) { vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 0; i <= n; i++) { // 遍历背包 for (int j = 1; j * j <= i; j++) { // 遍历物品 dp[i] = min(dp[i - j * j] + 1, dp[i]); } } return dp[n]; } }; // 先物品后背包 class Solution { public: int numSquares(int n) { vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 1; i * i <= n; i++) { // 遍历物品 for (int j = i * i; j <= n; j++) { // 遍历背包 dp[j] = min(dp[j - i * i] + 1, dp[j]); } } return dp[n]; } };
后言
- 今天这几题的递推公式有点感觉了,可惜初始化没想好过不了,继续加油吧~?
文章来源:https://blog.csdn.net/qq_56077562/article/details/135380167
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!