欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > IT业 > 3.31 代码随想录第三十一天打卡

3.31 代码随想录第三十一天打卡

2025/4/2 19:50:36 来源:https://blog.csdn.net/2401_87843408/article/details/146800420  浏览:    关键词:3.31 代码随想录第三十一天打卡

1049.最后一块石头的重量II

(1)题目描述:

(2)解题思路:

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {vector<int> dp(15001, 0);int sum = 0;for (int i = 0; i < stones.size(); i++) sum += stones[i];int target = sum / 2;for (int i = 0; i < stones.size(); i++) { // 遍历物品for (int j = target; j >= stones[i]; j--) { // 遍历背包dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[target] - dp[target];}
};

(3)总结:

1.石头相撞,把石头分为重量总和基本相等的两堆(比如看示例石头总和为23,那如果分为11和12的两队相撞后重量最小为1)
2.物品的数值即是重量又是价值
3.23/2==11向下取整,sum-z*11==1
4.dp[j]的定义是石头重量总和

494.目标和

(1)题目描述:

(2)解题思路:

1.一维数组方法
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (target + sum) / 2;vector<int> dp(bagSize + 1, 0);dp[0] = 1;for (int i = 0; i < nums.size(); i++) {for (int j = bagSize; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[bagSize];}
};

2.二维数组方法:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (target + sum) / 2;vector<vector<int>> dp(nums.size(), vector<int>(bagSize + 1, 0));// 初始化最上行if (nums[0] <= bagSize) dp[0][nums[0]] = 1; // 初始化最左列,最左列其他数值在递推公式中就完成了赋值dp[0][0] = 1; int numZero = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] == 0) numZero++;dp[i][0] = (int) pow(2.0, numZero);}// 以下遍历顺序行列可以颠倒for (int i = 1; i < nums.size(); i++) { // 行,遍历物品for (int j = 0; j <= bagSize; j++) { // 列,遍历背包if (nums[i] > j) dp[i][j] = dp[i - 1][j]; else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];}}return dp[nums.size() - 1][bagSize];}
};

(3)总结:

1.dp[j]  容量为j  有dp[j]种方法
题可以转化成我们常见的「背包模型」的问题。设我们最终选取的结果中,前面加 + 号的数字之和为 a ,前面加 - 号的数字之和为 b ,整个数组的总和为 sum ,于是我们有:
a + b = sum
a - b = target
上面两个式子消去 b 之后,可以得到 a = (sum + target) / 2
也就是说,我们仅需在 nums 数组中选择一些数,将它们凑成和为 (sum + target) / 2 即
可。问题就变成了 416. 分割等和子集 这道题。我们可以用相同的分析模式,来处理这道题。
1. 状态表示:
dp[i][j] 表示:在前 i 个数中选,总和正好等于 j ,一共有多少种选法。
2. 状态转移方程:
老规矩,根据「最后一个位置」的元素,结合题目的要求,我们有「选择」最后一个元素或者「不选择」最后一个元素两种策略:
不选 nums[i] :那么我们凑成总和 j 的总方案,就要看在前 i - 1 个元素中选,凑成总和为 j 的方案数。根据状态表示,此时 dp[i][j] = dp[i - 1][j] ;
选择 nums[i] :这种情况下是有前提条件的,此时的 nums[i] 应该是小于等于 j 。因为如果这个元素都比要凑成的总和大,选择它就没有意义呀。那么我们能够凑成总和为j 的方案数,就要看在前 i - 1 个元素中选,能否凑成总和为 j - nums[i] 。根据状态表示,此时 dp[i][j] = dp[i - 1][j - nums[i]]
综上所述,两种情况如果存在的话,应该要累加在一起。因此,状态转移方程为:
dp[i][j] = dp[i - 1][j]
if(nums[i - 1] <= j) dp[i][j]  += dp[i - 1][j - nums[i- 1]]
3. 初始化:
由于需要用到「上一行」的数据,因此我们可以先把第一行初始化。第一行表示不选择任何元素,要凑成目标和 j 。只有当目标和为 0 的时候才能做到,因此第一行仅需初始化第一个元素 dp[0][0] = 1
4. 填表顺序:
根据「状态转移方程」,我们需要「从上往下」填写每一行,每一行的顺序是「无所谓的」。
5. 返回值:
根据「状态表示」,返回 dp[n][aim] 的值。其中 n 表示数组的大小, aim 表示要凑的目标和。

474.一和零

(1)题目描述:

  

(2)解题思路:

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0for (string str : strs) { // 遍历物品int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') zeroNum++;else oneNum++;}for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历!for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
};

(3)总结:

1.dp[i][j]  i个0 j个1  最多能装dp[i][j]个物品

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词