解法

這題用01背包可以快速解出，和416題一樣，把總和的一半當(dāng)作容量，這樣能裝的物品的最大價(jià)值肯定是小于等于容量的，然后拿sum減去能容納的最大值，就是另一半的價(jià)值，兩者相減，就是剩余石頭的重量。

class?Solution?{

????public?int?lastStoneWeightII(int[]?stones)?{

????????int?m?=?stones.length;

????????int?sum?=?0;

????????for?(int?i?=?0;?i?<?m;?i++)?{

????????????sum?+=?stones[i];

????????}

????????int?target?=?sum?/?2;

????????int[]?dp?=?new?int[target?+?1];

????????for?(int?i?=?0;?i?<?m;?i++)?{

????????????//?倒序遍歷，這樣之前的dp[j?-?stones[i]]肯定沒有取過i

????????????for?(int?j?=?target;?j?>=?stones[i];?j--)?{

????????????????dp[j]?=?Math.max(dp[j],?dp[j?-?stones[i]]?+?stones[i]);

????????????}

????????}

????????return?sum?-?2?*?dp[target];

????}

}