描述

1049. 最后一塊石頭的重量 II
有一堆石頭，用整數(shù)數(shù)組 stones 表示。其中 stones[i] 表示第 i 塊石頭的重量。

每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎。假設(shè)石頭的重量分別為 x 和 y，且 x <= y。那么粉碎的可能結(jié)果如下：

如果 x == y，那么兩塊石頭都會被完全粉碎；
如果 x != y，那么重量為 x 的石頭將會完全粉碎，而重量為 y 的石頭新重量為 y-x。
最后，最多只會剩下一塊 石頭。返回此石頭 最小的可能重量 。如果沒有石頭剩下，就返回 0。

示例 1：

輸入：stones = [2,7,4,1,8,1]
輸出：1
解釋：
組合 2 和 4，得到 2，所以數(shù)組轉(zhuǎn)化為 [2,7,1,8,1]，
組合 7 和 8，得到 1，所以數(shù)組轉(zhuǎn)化為 [2,1,1,1]，
組合 2 和 1，得到 1，所以數(shù)組轉(zhuǎn)化為 [1,1,1]，
組合 1 和 1，得到 0，所以數(shù)組轉(zhuǎn)化為 [1]，這就是最優(yōu)值。
示例 2：

輸入：stones = [31,26,33,21,40]
輸出：5
示例 3：

輸入：stones = [1,2]
輸出：1

提示：
1 <= stones.length <= 30
1 <= stones[i] <= 100

思路一：動態(tài)規(guī)劃

最后一塊石頭的重量：從一堆石頭中,每次拿兩塊重量分別為x,y的石頭,若x=y,則兩塊石頭均粉碎;若x<y,兩塊石頭變?yōu)橐粔K重量為y-x的石頭求最后剩下石頭的最小重量(若沒有剩下返回0)
問題轉(zhuǎn)化為：把一堆石頭分成兩堆,求兩堆石頭重量差最小值
進(jìn)一步分析：要讓差值小,兩堆石頭的重量都要接近sum/2;我們假設(shè)兩堆分別為A,B,A<sum/2,B>sum/2,若A更接近sum/2,B也相應(yīng)更接近sum/2
進(jìn)一步轉(zhuǎn)化：將一堆stone放進(jìn)最大容量為sum/2的背包,求放進(jìn)去的石頭的最大重量MaxWeight,最終答案即為sum-2*MaxWeight;、
0/1背包最值問題：外循環(huán)stones,內(nèi)循環(huán)target=sum/2倒序,應(yīng)用轉(zhuǎn)移方程1

class Solution { public:int lastStoneWeightII(vector<int>& stones) {//轉(zhuǎn)化為01背包問題,就是分兩組,看那一組離容量sum/2最近int n = stones.size(); //獲取 int sum = 0;for(int i=0;i<stones.size();i++) sum+=stones[i]; //求數(shù)組中總重量int targert = sum/2;vector<int> dp(targert+1); //定義dp[i],返回容量為j時候裝石頭最大重量//開始01背包for(int i=0;i<n;i++){for(int j=targert;j>=stones[i];j--){dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);}}return sum-dp[targert] - dp[targert];} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode-动态规划背包题-1049. 最后一块石头的重量 II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。