游戏网站建设公司,小规模公司做网站成本是什么,开广告公司怎样跑生意,天元建设集团有限公司董事长张桂玉1049.最后一块石头的重量II 思路#xff1a;将石头分为两堆#xff0c;他们两个的重量最接近#xff0c;碰撞的话#xff0c;此时剩下的重量最小#xff0c;故此时想到动态规划#xff0c;但是我个人感觉很容易被陷入本道题的一些条件#xff0c;比如说xy#xff0…1049.最后一块石头的重量II 思路将石头分为两堆他们两个的重量最接近碰撞的话此时剩下的重量最小故此时想到动态规划但是我个人感觉很容易被陷入本道题的一些条件比如说xy想着要去区分每次拿出去的顺序什么的。这道题的关键是生成的dp[target]的含义是能从石头堆中取出的最靠近target的值。 class Solution {
public:int lastStoneWeightII(vectorint stones) {int sum0;for(int i0;istones.size();i){sumstones[i];}int targetsum/2;vectorint dp(target1,0);for(int i0;istones.size();i){for(int jtarget;jstones[i];--j){dp[j]max(dp[j],dp[j-stones[i]]stones[i]);}}return sum-dp[target]-dp[target];}
};494.目标和 思路这道题要将目标和进行分解分解成一个小数和一个大数但是这两个数的和是一定的即leftrightsumright-lefttarget这样的一个关系那么rightsum-leftleft(sumtarget)/2故这个left就是要求的值。若不能分解成left那么可知是不可能通过加减运算得到结果的。记一个key:dp[j]dp[j-nums[i]];求组合的递推公式标准写法 class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum0;for(int i0;inums.size();i){sumnums[i];}if((sumtarget)%21)return 0;if(abs(target)sum)return 0;int bagsize(targetsum)/2;vectorint dp(bagsize1,0);dp[0]1;for(int i0;inums.size();i){for(int jbagsize;jnums[i];j--){dp[j]dp[j-nums[i]];}}return dp[bagsize];}
};474.一和零 思路二维的01背包问题统计每个字符串中的0和1然后利用递推公式进行dp[i][j]max(dp[i][j],dp[i-zeronum][j-onenum]1)得到每个dp[i][j]的最大子集 class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m1,vectorint(n1,0));for(string str:strs){int zeronum0;int onenum0;for(char s:str){if(s0)zeronum;else onenum;}for(int im;izeronum;i--){for(int jn;jonenum;j--){dp[i][j]max(dp[i][j],dp[i-zeronum][j-onenum]1);}}}return dp[m][n];}
};
