好用的小程序推荐_中关村标准化协会_app推广赚钱_宁波seo推广优化公司

1049.

有点难想，需要把石头分成两组按照背包的模式去想。

/** @lc app=leetcode.cn id=1049 lang=cpp** [1049] 最后一块石头的重量 II*/// @lc code=start
#include<iostream>
#include<vector>
using namespace std;
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];}
};
// @lc code=end

 494.

有点难...

/** @lc app=leetcode.cn id=494 lang=cpp** [494] 目标和*/// @lc code=start
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum=0;for(int a:nums){sum+=a;}if((sum+target)%2==1)return 0;if(abs(target)>sum)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]=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];}
};
// @lc code=end

474.

/** @lc app=leetcode.cn id=474 lang=cpp** [474] 一和零*/// @lc code=start
#include<iostream>
#include<vector>
#include<string>
using namespace std;
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>>dp(m+1,vector<int>(n+1,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];}
};
// @lc code=end