本文主要是介绍代码随想录-动态规划5（1049. 最后一块石头的重量 II、494. 目标和、474. 一和零），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1049. 最后一块石头的重量 II
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int target = 0;int flag = 0;for (int i=0; i<stones.size();i++){target += stones[i];}vector<int> dp(target/2+1, 0);for (int i=0; i<stones.size();i++){for (int j=target/2; j>0;j--){if (i==0) {if (j>=stones[i]) dp[j]=stones[i];}else{if (j-stones[i]<0) dp[j]=dp[j];else dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]);}}}return target - dp[target/2] - dp[target/2];}
};494. 目标和
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {if (nums.size()==1 && nums[0]==abs(target)) return 1;if (nums.size()==1 && nums[0]!=abs(target)) return 0;int sum = 0;for (int i=0; i<nums.size(); i++){sum += nums[i];}if ((target+sum)%2!=0) return 0;if (abs(target) > sum) return 0;int mid = (target+sum)/2;vector<int> dp(mid+1, 0);dp[0] = 1;// for (int i=0; i<dp.size(); i++)// {// if (i==nums[0]) dp[i] = 1;// }for (int i=0; i<nums.size(); i++){for (int j=mid; j>=0; j--){if (j-nums[i]>=0) dp[j] = dp[j] + dp[j-nums[i]];}}return dp[mid];}
};474. 一和零
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m+1, vector<int>(n+1, 0));unordered_map<char,int> hash;for (int s=0; s<strs.size(); s++){hash.clear();for (int h=0; h<strs[s].size(); h++){hash[strs[s][h]]++;}for (int i=m; i>=0; i--){for (int j=n; j>=0; j--){dp[i][j] = max(dp[i][j], i-hash['0']>=0&&j-hash['1']>=0?dp[i-hash['0']][j-hash['1']]+1:0);}}}return dp[m][n];}
};这篇关于代码随想录-动态规划5（1049. 最后一块石头的重量 II、494. 目标和、474. 一和零）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
