1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
const int n = stones.size();
int sum = 0;
for (auto stone : stones) sum += stone;
int t = sum / 2;
vector<int> f(t + 1);
for (int i = 1; i <= n; ++i) {
int x = stones[i - 1];
for (int j = t; j >= x; --j) {
f[j] = max(f[j], f[j - x] + x);
}
}
return sum - f[t] - f[t];
}
};
|