开发网站能赚多少钱,网页制作与设计课本,腾讯做网站,在那些网站可以接兼职做目录
一、#xff08;leetcode 1049#xff09;最后一块石头的重量II
二、#xff08;leetcode 494#xff09;目标和
三、#xff08;leetcode 474#xff09;一和零 一、#xff08;leetcode 1049#xff09;最后一块石头的重量II
力扣题目链接 状态#xff1a;…目录
一、leetcode 1049最后一块石头的重量II
二、leetcode 494目标和
三、leetcode 474一和零 一、leetcode 1049最后一块石头的重量II
力扣题目链接 状态查看思路后AC。 将石头重量分成两堆这两堆的重量要尽可能相近。计算其中一堆的最大重量因为sum/2向下取整所以dp[target]肯定是重量较轻的那一堆最后的答案就是重量较大的那一堆减去dp得到的这一堆也就是(sum-dp[target]) - dp[target]。
class Solution {
public:int lastStoneWeightII(vectorint stones) {int sum 0, len stones.size();for(int i 0; i len; i){sum stones[i];}int target sum / 2;vectorint dp(15001, 0);for(int i 0; i len; 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目标和
力扣题目链接 状态不会。 原题的回溯方法比较符合直觉很难在没有做过的情况下和01背包或者说分割等和子集的方法联系起来。要多好好想想
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0, len nums.size();for(int i 0; i len; i) { sum nums[i]; }if(abs(target) sum) return 0;if((targetsum) % 2 1) return 0;int bagsize target sum 1;vectorint dp(bagsize1, 0);dp[0] 1;for(int i 0; i len; i){for(int j bagsize; j nums[i]; --j){dp[j] dp[j-nums[i]];}}return dp[bagsize];}
};
三、leetcode 474一和零
力扣题目链接 状态不会。 不要因为有m和n的限制就觉得这是多重背包这里的m和n只是不同维度上的限制题目本质上还是01背包但是怎么关联上还是有困难啊。
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m1, vectorint(n1, 0));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);}}}return dp[m][n];}
};
