LeetCode1049. 最后一块石头的重量 II

题目

分析

本题和分割等和子集题目有异曲同工之妙。本题就是将石头尽可能分成重量相同的两堆，使得这两堆重量相减之后结果最小。这就转化为了分割相同等和子集的题目。

代码

二维dp数组

 1 class Solution {
 2 public:
 3     int lastStoneWeightII(vector<int>& stones) {
 4         int sum = 0;
 5         for(auto s:stones) sum += s;
 6         int tmp = sum;
 7         sum /= 2;
 8         int dp[stones.size()][sum+1];
 9         //初始化
10         memset(dp,0,sizeof(dp));
11         for(int j = 0;j <= sum;j++){
12             if(j >= stones[0]) dp[0][j] = stones[0];
13         }
14         for(int i = 1;i < stones.size();i++){
15             for(int j = 0;j <= sum;j++){
16                 if(j < stones[i] ) dp[i][j] = dp[i-1][j];
17                 else dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i]] + stones[i]);
18             }
19         }
20         return tmp - 2 * dp[stones.size()-1][sum] ;
21     }
22 };

一维dp数组

动态转移公式 dp[j] = max(dp[j],dp[j-stones[i]] + stones[i]);

 1 class Solution {
 2 public:
 3     int lastStoneWeightII(vector<int>& stones) {
 4         vector<int>dp(30*1000/2 + 1,0); //30*1000/2是最大容量
 5         int sum = 0;
 6         for(auto s:stones){
 7             sum += s;
 8         }
 9         int tmp = sum;
10         sum /= 2;
11         for(int i = 0;i < stones.size();i++){
12             for(int j = sum;j >= stones[i];j--){
13                 dp[j] = max(dp[j],dp[j-stones[i]] + stones[i]);
14             }
15         }
16         return tmp - 2*dp[sum];
17     }
18 };