16 lines
436 B
C++
16 lines
436 B
C++
#include "s1049_last_stone_weight_ii.hpp"
|
|
|
|
int S1049::lastStoneWeightII(vector<int>& stones) {
|
|
int total{0};
|
|
int len = stones.size();
|
|
vector<int> dp(30 * 1000 / 2 + 1, 0);
|
|
for (int i{0}; i < len; ++i) total += stones[i];
|
|
int limit = total >> 1;
|
|
for (int i{0}; i < len; ++i) {
|
|
for (int j = limit; j >= stones[i]; --j) {
|
|
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
|
|
}
|
|
}
|
|
return total - dp[limit] * 2;
|
|
}
|