1049. 最后一塊石頭的重量 II
題目鏈接： 1049. 最后一塊石頭的重量 II - 力扣（LeetCode）
文章講解： 代碼隨想錄
思路：
理解為把石頭分成兩堆 使得兩堆的差值盡可能小 求這個最小值1
理解為往背包里裝物品?
每個物品的重量為石頭的重量 價值也為石頭的價值??
dp[i][j]表示從0-i塊石頭往容量為j的包里裝 的最大價值
狀態轉移：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-cost[i]]+weight[i])
壓縮成一維
然后dp[j]表示容量為j的背包能裝的石頭的最大價值
那么sum-dp【j】就是另一個背包的石頭的重量
做差求最小值即為所求
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum=0;for(auto x:stones){sum+=x;}vector<int>dp(3001,0);for(int i=0;i<stones.size();i++){for(int j=sum;j>=stones[i];j--){dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);}}int min=30000;for(int i=0;i<=sum;i++){int diff=abs((sum-dp[i])-dp[i]);if(diff<min) min=diff;}return min;}
};494. 目標和
題目鏈接：494. 目標和 - 力扣（LeetCode）
文章講解：代碼隨想錄
思路：
相當于分成兩堆
用正的一堆減負的一堆等于目標
left-right=target
又right=sum-left
從而
left=（sum+target）/2
定義dp【j】表示容量為j的背包有多少種裝法
重點是遞推公式
dp【j】+=dp【j-nums【i】】
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum=0;for(auto x:nums){sum+=x;}int left=(target+sum)/2;if((target+sum)%2!=0)return 0;if(target+sum<0)return 0;vector<int>dp(1001,0);dp[0]=1;for(int i=0;i<nums.size();i++){for(int j=dp.size()-1;j>=nums[i];j--){dp[j]+=dp[j-nums[i]];}}return dp[left];}
};總結：
一緯dp數組j的順序不能正序遍歷的原因在于遞推公式
dp【j】=max（dp【j】，dp【j-nums【i】+weights【i】】）
這里涉及到更新dp【j】順序的問題? 小的j會影響大的j
d的j不會影響小的j 所以應該先更新大j
474.一和零
題目鏈接：474. 一和零 - 力扣（LeetCode）
文章講解：代碼隨想錄
思路：
事實上 這道題就是多維度的01背包
每個字符串的價值是1
有兩個維度的重量m和n
dp【m-x】【n-y】+1表示裝物品i? ? ? ?dp【m】【n】表示不裝物品i
定義dp【m】【n】表示不超過m個0和n個1的情況下最大子集的長度
dp【m】【n】=max（dp【m-x】【n-y】+1，dp【m】【n】）
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>>dp(101,vector<int>(101,0));for(auto s:strs){int x=0;int y=0;for(auto c:s){if(c=='0'){x++;}else{y++;}}for(int i=dp.size()-1;i>=x;i--){for(int j=dp[0].size()-1;j>=y;j--){dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1);}}}return dp[m][n];}
};
 iot-core)
