算法学习day43
- 1. 力扣1049. 最后一块石头的重量 II
- 1.1 分析
- 1.2 代码
- 2. 力扣494. 目标和
- 2.1 分析
- 2.2 代码
- 3. 力扣474.一和零
- 3.1 分析
- 3.2 代码
- 4.参考资料
1. 力扣1049. 最后一块石头的重量 II
1.1 分析
动规五部曲：
1.确定dp数组以及下标的含义
dp[j]表示容量为j的背包，最多可以背最大的重量为dp[j]
本题中石头的重量是stones[i]，石头的价值也是stones[i]
2.确定递推公式
01背包的递推公式为:dp[j] = max(dp[j] , dp[j -weitght[i]] + value[i])
本题为：dp[j] = max(dp[j] , dp[j - stones[i]] + stones[i])
3.dp数组如何初始化
dp[j] 中的j表示容量，最大容量时多少？是所有石头重量的总和。
题目描述：1 <= stones.length <= 30 1 <= stones[i] <= 100, 最大重量30 * 100 = 3000。
dp数组开到1500即可。
初始化dp[j]，重量不为负数，dp[j]全部初始化为0即可。
vector<int> dp(1501 , 0);
4.确定遍历顺序
如果使用一维dp数组，物品遍历在外，背包遍历在内。不能交换！内层for循环倒序遍历。
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]);
}
}
5.举例推导dp数组
1.2 代码
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
// 定义一个大小为1501的数组作为背包数组
vector<int> dp(1501, 0);
int sum = 0;
// 遍历数组， 计算所有石头的总重量
for(int i = 0 ; i < stones.size() ; i++){
sum += stones[i];
}
// 计算背包容量，即总重量的一半
int target = sum / 2;
// 01背包
for(int i = 0 ; i < stones.size(); i++){// 遍历物品
for(int j = target; j>=stones[i]; j--){// 遍历背包
// 递推公式：dp[j]表示背包容量为j时可以得到的最大价值
// max(dp[j], dp[j - stones[i]] + stones[i])表示在不选当前石头时，背包容量为j时的最大价值。
// 以及在选了当前石头时，背包容量为j时的最大价值。取二者之间的较大值，为当前背包容量下的最大价值。
dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]);
}
}
return sum - dp[target] - dp[target];
}
};
2. 力扣494. 目标和
2.1 分析
动规五部曲：
1.确定dp数组以及下标的含义
假设加法总和x, 那么减法对应的总和为sum - x
所以我们求 x - (sum - x) = target
推导出： x=(target + sum) / 2
问题转换为装满容量为x的背包有几种方法？
dp[j]: 装满容量为j的背包，有dp[j] 种方法。
2.dp数组的递推公式
dp[j] 里面数j就是要求的大小。
举个栗子：dp[5] 5是要凑的大小。如果知道nums[i] = 1， 5 - 1= 4 ， 按照1中的定义有dp[5-1]种方法凑成容量为5的背包
如果知道nums[i] = 2， 5 - 2= 3 ， 按照1中的定义有dp[5-2]种方法凑成容量为5的背包
如果知道nums[i] = 3， 5 - 3= 2 ， 按照1中的定义有dp[5-3]种方法凑成容量为5的背包
如果知道nums[i] = 4， 5 - 4= 1 ， 按照1中的定义有dp[5-4]种方法凑成容量为5的背包
如果知道nums[i] = 5， 5 - 5= 0 ， 按照1中的定义有dp[5-5]种方法凑成容量为5的背包
递推公式：dp[j] +=dp[j - nums[i]]
3.dp数组如何初始化
由递推公式可知：dp[0] = 1 在公式中，如果dp[0] = 0 ,那么递推结果将都是0.
4.dp数组遍历顺序
nums放在外循环，target内循环，且内循环倒序遍历。
5.举例推导dp数组
2.2 代码
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (abs(S) > sum) return 0; // 如果目标值的绝对值超过数组元素和，无法得到方案，返回0
if ((S + sum) % 2 == 1) return 0; // 如果目标值和数组元素和的和是奇数，无法得到方案，返回0
int bagSize = (S + sum) / 2; // 计算背包大小
vector<int> dp(bagSize + 1, 0); // 初始化动态规划数组
dp[0] = 1; // dp数组初始化
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]; // 返回得到目标值的方案数
}
};
3. 力扣474.一和零
3.1 分析
动规五部曲：
1.确定dp数组以及下标的含义
dp[i] [j]: 最多有i个0和j个1的strs最大子集的大小为dp[i] [j]
2.确定递推公式
dp[i] [j] 可以由前一个strs里的字符串推导出来，str里的字符串有zeroNum个0， oneNum个1。
dp[i] [j] 可以是dp[i - zeroNum] [j - oneNum] + 1；注意：前一个，所以加1。
然后在遍历的过程中，取dp[i] [j]的最大值。
递推公式:dp[i] [j] = max(dp[i] [j] , dp[i -zeroNum] [j - oneNum] + 1)
3.dp数组如何初始化
初始为0，保存递推的时候dp[i] [j] 不会被初始值覆盖
4.确定遍历顺序
外层for循环遍历物品，内层for循环遍历背包容量，且从后向前遍历。
本题中物品就是strs中的字符串，背包容量就是题目描述的m、n.
for(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);
}
}
}
5.举例推导dp数组
3.2 代码
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 创建一个 m+1 行，n+1 列的二维数组 dp，并初始化为 0
for (string str : strs) { // 遍历字符串数组 strs，每个字符串作为一个物品
int oneNum = 0, zeroNum = 0; // 统计当前字符串中 1 和 0 的个数
for (char c : str) {
if (c == '0') zeroNum++;
else oneNum++;
}
for (int i = m; i >= zeroNum; i--) { // 遍历物品容量，从 m 到 zeroNum，且从后向前遍历
for (int j = n; j >= oneNum; j--) { // 遍历背包容量，从 n 到 oneNum，且从后向前遍历
// 计算状态转移方程：当前背包容量为 i 和 j 时，最多可以装多少个字符串
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n]; // 返回 dp[m][n]，即背包容量为 m 和 n 时最多可以装多少个字符串
}
};
4.参考资料
[代码随想录]
