代理记账网站模板,东莞微信网站建设动态,重庆新闻经典论坛,苏州建设交通高等职业技术学院【25届秋招备战C】题型练习-背包问题 0-1背包416 - 分割等和子集1049 - 最后一块石头的重量 Ⅱ494 - 目标和474- 一和零 完全背包518- 零钱兑换Ⅱ377- 组合总数Ⅱ322- 零钱兑换279- 完全平方数 参考 0-1背包
416 - 分割等和子集
链接: 分割等和子集 解题思路#xff1a;给定… 【25届秋招备战C】题型练习-背包问题 0-1背包416 - 分割等和子集1049 - 最后一块石头的重量 Ⅱ494 - 目标和474- 一和零 完全背包518- 零钱兑换Ⅱ377- 组合总数Ⅱ322- 零钱兑换279- 完全平方数 参考 0-1背包
416 - 分割等和子集
链接: 分割等和子集 解题思路给定容量判断是否可以满足固定的价值 分割等和问题只需要求和取一半作为结果即可总和为奇直接返回false此题关键在于背包价值的遍历顺序代码随想录的解释每一个元素一定是不可重复放入所以从大到小遍历很妙 1.确定dp数组以及下标的含义 dp[j] 表示j容量能装的最大价值有dp[j]种方法 2.确定递推公式 dp[j]max(dp[j],dp[j-nums[i]]nums[i]) 装满j容量的方法数统一公式 3.dp数组如何初始化 dp[0]1非零下标初始为0 4.确定遍历顺序 对于01背包问题一维dp的遍历nums放在外循环target在内循环且内循环倒序。
class Solution {
public:bool canPartition(vectorint nums) {vectorint dp(10001,0);int sum0;for(int i0;inums.size();i){sum nums[i];}if (sum % 2 1) return false;sumsum/2;for(int i0;inums.size();i){for(int jsum;jnums[i];j--){dp[j]max(dp[j],dp[j-nums[i]]nums[i]);}}if(dp[sum]sum){return true;}return false;}
};1049 - 最后一块石头的重量 Ⅱ
链接: 最后一块石头的重量 Ⅱ 解题思路其实就是分割等和的变体只要找到尽可能平分的背包即可。
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];}
};494 - 目标和
链接: 目标和 解题思路总容量固定的方法数 分为两个子集两包和为target设其中一包的和为x则另一包的和为sum-x且x-sum-xtarget即xtagetsum/2即只需要求解总容量为targetsum/2的可能方法数 1.确定dp数组以及下标的含义 dp[j] 表示装满j容量有dp[j]种方法 2.确定递推公式 dp[j] dp[j - nums[j]] 装满j容量的方法数统一公式 3.dp数组如何初始化 dp[0]1非零下标初始为0 4.确定遍历顺序 对于01背包问题一维dp的遍历nums放在外循环target在内循环且内循环倒序。
class Solution {
public:int findTargetSumWays(vectorint nums, int S) {int sum 0;for (int i 0; i nums.size(); i) sum nums[i];if (abs(S) sum) return 0; // 此时没有方案if ((S sum) % 2 1) return 0; // 此时没有方案int bagSize (S 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];}
};474- 一和零
链接: 一和零 解题思路满足最多m个0n个1最多有多少个物品
1.确定dp数组以及下标的含义 dp[i][j] 表示i个0j个1最多装dp[i][j]个物品 2.确定递推公式 dp[i][j]max(dp[i-x][j-y]1,dp[i][j]) (每个物品的重量是x个0y个1) 3.dp数组如何初始化 dp[0][0]0非零下标初始为0 4.确定遍历顺序 对于01背包问题二维dp的遍历nums放在外循环target在内循环且内循环倒序。 先遍历物品再遍历背包
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m1,vectorint(n1,0));for(string str:strs){int x0,y0;for(char c:str){if(c0) x;else y;}for(int im;ix;i--){for(int jn;jy;j--){dp[i][j]max(dp[i][j],dp[i-x][j-y]1);}}}return dp[m][n];}
};完全背包
518- 零钱兑换Ⅱ
链接: 零钱兑换Ⅱ 解题思路思路同目标和注意初始化dp[0]1其实是为了迎合递推公式没有实际意义
1.确定dp数组以及下标的含义 dp[j] 表示装满j容量有dp[j]种方法 2.确定递推公式 dp[j] dp[j - nums[j]] 装满j容量的方法数统一公式 3.dp数组如何初始化 dp[0]1非零下标初始为0 4.确定遍历顺序 完全背包正序先物品再背包不会重复是组合数先背包再物体有顺序是排列数。
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount1,0);dp[0]1;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){dp[j]dp[j-coins[i]];}}return dp[amount];}
};377- 组合总数Ⅱ
链接: 组合总数Ⅱ 解题思路思路同零钱兑换Ⅱ唯一不同是本题强调顺序注意初始化dp[0]1其实是为了迎合递推公式没有实际意义
1.确定dp数组以及下标的含义 dp[j] 表示装满j容量有dp[j]种方法 2.确定递推公式 dp[j] dp[j - nums[j]] 装满j容量的方法数统一公式 C测试用例有两个数相加超过int的数据所以需要在if里加上dp[i] INT_MAX - dp[i - num]。 3.dp数组如何初始化 dp[0]1非零下标初始为0 4.确定遍历顺序 完全背包正序先物品再背包不会重复是组合数先背包再物体有顺序是排列数。
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount1,0);dp[0]1;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){dp[j]dp[j-coins[i]];}}return dp[amount];}
};322- 零钱兑换
链接: 零钱兑换 解题思路思路同零钱兑换Ⅱ但这里是最小值则初始化时需要给定INT_MAX且递推公式也要用min取最小
1.确定dp数组以及下标的含义 dp[j] 表示装满j容量最少有dp[j]个物品 2.确定递推公式 dp[j] mindp[j - nums[j]]1dp[j] C测试用例有两个数相加超过int的数据所以需要在if里加上dp[i] INT_MAX - dp[i - num]。 3.dp数组如何初始化 dp[0]1非零下标初始为0 4.确定遍历顺序 完全背包正序先物品再背包不会重复是组合数先背包再物体有顺序是排列数。
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint 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] min(dp[j - coins[i]] 1, dp[j]);}}}if (dp[amount] INT_MAX) return -1;return dp[amount];}
};279- 完全平方数
链接: 完全平方数 解题思路思路同零钱兑换但这里是最小值则初始化时需要给定INT_MAX且递推公式也要用min取最小
1.确定dp数组以及下标的含义 dp[j] 表示装满j容量最少有dp[j]个物品 2.确定递推公式 dp[j] mindp[j - nums[j]]1dp[j] C测试用例有两个数相加超过int的数据所以需要在if里加上dp[i] INT_MAX - dp[i - num]。 3.dp数组如何初始化 dp[0]1非零下标初始为0 4.确定遍历顺序 完全背包正序先物品再背包不会重复是组合数先背包再物体有顺序是排列数。
public:int numSquares(int n) {vectorint 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];}
};参考
代码随想录救我狗命 链接: 代码随想录
