本文涉及知识点

C++动态规划
C++背包问题

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

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
示例 2：
输入：stones = [31,26,33,21,40]
输出：5
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 100

动态规划 01背包

性质一：将石头分成A、B组，如果A组的质量小于B组则交换AB组。每次碰撞都从AB组各取一个碰撞，碰撞剩余的石头归还原组。碰撞后剩余石头的质量一定为x=$\sum (a)-\sum (b)$。 每次碰撞AB组都减少相同的质量，直到B组的质量为0。
性质二：x > max(a)，则最优一定剩余2块或更多石头。石头质量不会增加，故块石头的质量一定小于等于max(a)。
性质三：x <= max(a)，则一定能剩余0或1块石头。从a组取出max(a)后ab组碰撞，b组剩余[0,max(a)]和max(a）碰撞。
性质四：会不会某块石头，某次碰撞后，从A组移动B组？ 会，但无需枚举。
不失一般性，这块石头是由a,b,c,d碰撞成的，在碰撞前将a,b,c,d换组效果完全一样。
性质二的情况无需手动排除，会被更优方案淘汰，比如：将max(a)移到b组。

动态规划的状态表示

dp[i][s] 表示，从前i块石头中选择若干石头总重量为s的方案是否存在。空间复杂度：O(nS) ,S是a之和。

动态规划的转移方程

枚举前置状态
dp[i+1] = dp[i] 不选择第i块石头
dp[i+1][s+nums[i]] ||= dp[i][s] 选择第i块石头

动态规程的初始值

dp[0][0]=true。

动态规划的填报顺序

i = 0 To n-1 sum = 0 To S-nums[i]

动态规划的返回值

dp.back()[s] 为true。
min(bas(S-2s))

代码

核心代码

class Solution {
		public:
			int lastStoneWeightII(vector<int>& stones) {
				const int N = stones.size();
				const auto& S = accumulate(stones.begin(), stones.end(),0);
				vector<vector<bool>> dp(N + 1, vector<bool>(S + 1));
				dp[0][0] = true;
				for (int i = 0; i < N; i++) {
					dp[i + 1] = dp[i];
					for (int s = 0; s + stones[i] <= S; s++) {
						if (!dp[i][s])continue;
						dp[i + 1][s + stones[i]] = true;
					}
				}
				int iMin = INT_MAX;
				for (int s = 0; s <= S; s++) {
					if (!dp.back()[s])continue;
					iMin = min(iMin, abs(S - 2 * s));
				}
				return iMin;
			}
		};

单元测试

vector<int> stones;
		TEST_METHOD(TestMethod1)
		{
			stones = { 2, 7, 4, 1, 8, 1 };
			auto res = Solution().lastStoneWeightII(stones);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			stones = { 31,26,33,21,40};
			auto res = Solution().lastStoneWeightII(stones);
			AssertEx(5, res);
		}