LeetCode Solutions
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
const int sum = accumulate(begin(stones), end(stones), 0);
vector<bool> dp(sum + 1);
dp[0] = true;
int s = 0;
for (int stone : stones)
for (int w = sum / 2; w > 0; --w) {
if (w >= stone)
dp[w] = dp[w] || dp[w - stone];
if (dp[w])
s = max(s, w);
}
return sum - 2 * s;
}
};
|
class Solution {
public int lastStoneWeightII(int[] stones) {
final int sum = Arrays.stream(stones).sum();
boolean[] dp = new boolean[sum + 1];
dp[0] = true;
int s = 0;
for (int stone : stones)
for (int w = sum / 2; w > 0; --w) {
if (w >= stone)
dp[w] = dp[w] || dp[w - stone];
if (dp[w])
s = Math.max(s, w);
}
return sum - 2 * s;
}
}
|
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
summ = sum(stones)
s = 0
dp = [True] + [False] * summ
for stone in stones:
for w in range(summ // 2 + 1)[::-1]:
if w >= stone:
dp[w] = dp[w] or dp[w - stone]
if dp[w]:
s = max(s, w)
return summ - 2 * s
|
