网站维护总结,用html制作个人简历,wordpress网站搬家vps,wordpress 喜欢插件目录 LeetCode:1049. 最后一块石头的重量 II
基本思路
C代码
LeetCode:494. 目标和
基本思路
C代码
LeetCode:474.一和零
基本思路
C代码 LeetCode:1049. 最后一块石头的重量 II 力扣代码链接 文字讲解#xff1a;LeetCode:1049. 最后一块石头的重量 II 视频讲解…目录 LeetCode:1049. 最后一块石头的重量 II
基本思路
C代码
LeetCode:494. 目标和
基本思路
C代码
LeetCode:474.一和零
基本思路
C代码 LeetCode:1049. 最后一块石头的重量 II 力扣代码链接 文字讲解LeetCode:1049. 最后一块石头的重量 II 视频讲解动态规划之背包问题这个背包最多能装多少 基本思路 本题其实就是尽量让石头分成重量相同的两堆相撞之后剩下的石头最小这样就化解成01背包问题了。其中石头的重量为stones[i]物品的价值也为stones[i]对应着01背包里的物品重量weight[i]和物品价值value[i]。
确定dp数组以及下标的含义 dp[j]的含义容量为j的背包最多可以装的价值为 dp[j]。而价值其实也就是背包中能够承载的石头的最大重量。
确定递推公式 01背包的递推公式为dp[j] max(dp[j], dp[j - weight[i]] value[i]);而这里的weight[i]和value[i]实际上都是stone[i]也就是石头的重量。因此递推公式可以写成dp[j] max(dp[j], dp[j - stones[i]] stones[i]);
dp数组如何初始化 既然 dp[j]中的j表示容量那么最大容量重量是多少呢就是所有石头的重量和。根据提示易知我们要求的target其实只是最大重量的一半也就是15000。接下来就是如何初始化dp[j]呢因为重量都不会是负数所以dp[j]都初始化为0就可以了。
vectorint dp(15001, 0);
确定遍历顺序 因为采用的是一维dp数组的方式因此遍历物品的for循环放在外层而变量背包容量大小的for循环放在内层并且要保证内层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]);}
}最后dp[target]就是容量为target的背包所能背的最大重量。在计算target的时候target sum / 2 因为是向下取整所以sum - dp[target] 一定是大于等于dp[target]的。
C代码
class Solution {
public:int lastStoneWeightII(vectorint stones) {vectorint 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];}
};
LeetCode:494. 目标和 力扣代码链接 文字讲解LeetCode:494. 目标和 视频讲解动态规划之背包问题装满背包有多少种方法 基本思路 最容易想到的就是回溯算法但是使用回溯算法容易超时。
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex) {if (sum target) {result.push_back(path);}// 如果 sum candidates[i] target 就终止遍历for (int i startIndex; i candidates.size() sum candidates[i] target; i) {sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i 1);sum - candidates[i];path.pop_back();}}
public:int findTargetSumWays(vectorint nums, int S) {int sum 0;for (int i 0; i nums.size(); i) sum nums[i];if (S sum) return 0; // 此时没有方案if ((S sum) % 2) return 0; // 此时没有方案两个int相加的时候要格外小心数值溢出的问题int bagSize (S sum) / 2; // 转变为组合总和问题bagsize就是要求的和// 以下为回溯法代码result.clear();path.clear();sort(nums.begin(), nums.end()); // 需要排序backtracking(nums, bagSize, 0, 0);return result.size();}
};我们如果使用动态规划的方法可以假设正数的总和为x负数的总和为y所有元素的绝对值之和为sum目标和为target。那么易得 可以得到 这里的x实际上就是背包容量BagSize。和之前的方法不同的地方在于前面的题是求容量为j的背包最多能装下多少。而这个题目是求装满容量为j的背包一共有多少种方法。
确定dp数组以及下标的含义 dp[j]表示装满容量为j的背包一共有dp[j]种方法。
确定递推公式 dp[j] dp[j] dp[j-nums[i]],可以理解为不包含物品i为上一次循环中的dp[j]和包含物品i的dp[j-nums[i]]。
dp数组如何初始化 这里dp[0] 同样初始为1 ,即装满背包为0的方法有一种放0件物品。并且如果背包容量j和物品0的大小相同此时dp[nums[i]] 1。
确定遍历顺序 遍历物品放在外循环遍历背包在内循环且内循环倒序为了保证物品只使用一次。
C代码
class Solution {
public:int findTargetSumWays(vectorint 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;vectorint 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];}
};
LeetCode:474.一和零 力扣代码链接 文字讲解LeetCode:474.一和零 视频讲解动态规划之背包问题装满这个背包最多用多少个物品 基本思路 这个题目依旧是一个01背包问题。但是需要统计每个字符串元素的0和1的数量也就是两个维度的背包。
确定dp数组以及下标的含义 dp[i][j]最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
确定递推公式 dp[i][j] 可以由前一个strs里的字符串推导出来strs里的字符串有zeroNum个0oneNum个1。dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] 1。 所以递推公式dp[i][j] max(dp[i][j], dp[i - zeroNum][j - oneNum] 1);
dp数组如何初始化 01背包的dp数组初始化为0就可以。因为物品价值不会是负数初始为0保证递推的时候dp[i][j]不会被初始值覆盖。
确定遍历顺序 在本题中物品就是strs里的字符串背包容量是题目描述中的m和n分别代表了dp数组的两个维度。
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);}}
}
举例推导dp数组 以输入[10,0001,111001,1,0]m 3n 3为例 C代码
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint (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];}
};
