Skip to content

1049. Last Stone Weight II 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int lastStoneWeightII(vector<int>& stones) {
    const int sum = accumulate(stones.begin(), stones.end(), 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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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