最后一块石头的重量
本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
本题物品的重量为store[i]，物品的价值也为store[i]。
动态规划（二维数组）
找到总重量最接近sum/2 的背包，这是一个石头堆。
和另一个堆相减，就是剩下的
class Solution { public: int lastStoneWeightII(vector<int>& stones) { if(stones.size() == 1 ) return stones[0]; int sum = 0; for(auto it:stones) sum += it; vector<vector<int>> dp (stones.size() , vector<int>( sum /2 + 1 , 0) ) ; for(int j=1 ; j<=sum/2 ;j++) if(j>=stones[0]) dp[0][j] = stones[0]; //找到背包为sum/2以内最大的种类 for(int i=1 ;i<stones.size() ;i++) { for(int j=1 ; j<=sum/2 ;j++) { if(j>=stones[i]) dp[i][j] = max( dp[i-1][j] , dp[i-1][j-stones[i]] + stones[i]); else dp[i][j] = dp[i-1][j]; } } //找到最接近sum/2的背包 int bag_max = 0; for(int i=0 ;i<stones.size() ;i++ ) { if(dp[i][sum/2] > bag_max) bag_max = dp[i][sum/2]; } //计算石头堆的差 return (sum - bag_max) - bag_max; } };
动态规划（滚动数组）
class Solution { public: int lastStoneWeightII(vector<int>& stones) { if(stones.size() == 1 ) return stones[0]; int sum = 0; for(auto it:stones) sum += it; vector<int> dp (sum /2 + 1 , 0); for(int i=0 ;i<stones.size() ;i++) { for(int j=sum/2 ; j>=0 ;j--) { if(j>=stones[i]) dp[j] = max( dp[j] , dp[j-stones[i]] + stones[i]); else dp[j] = dp[j]; } } return (sum - dp[sum/2]) - dp[sum/2]; } };
二刷
class Solution { public: int lastStoneWeightII(vector<int>& stones) { int sum = 0; for(auto it:stones) sum += it; // cout<<sum<<' '<<sum/2<<endl; vector<int> dp(sum/2+1,0); for(int i=0 ; i<stones.size();i++) { for(int j=sum/2 ; j>=stones[i];j--) { dp[j] = max(dp[j] , dp[j-stones[i]] + stones[i]); } } // cout<<dp[sum/2]; return sum - 2*dp[sum/2]; } };
