Last Stone Weight II LeetCode solution in C++

1
class Solution {
2
 public:
3
  int lastStoneWeightII(vector<int> &stones) {
4
    int n = stones.size();
5
    int sum = 0;
6
    for (int i = 0; i < n; i++) {
7
      sum += stones[i];
8
    }
9

10
    int dp[n + 1][sum + 1];
11
    for (int i = 0; i < n + 1; i++) {
12
      for (int j = 0; j < sum + 1; j++) {
13
        if (i == 0) dp[i][j] = 0;
14
        if (j == 0) dp[i][j] = 1;
15
      }
16
    }
17
    for (int i = 1; i < n + 1; i++) {
18
      for (int j = 1; j < sum + 1; j++) {
19
        if (stones[i - 1] <= j) {
20
          dp[i][j] = dp[i - 1][j - stones[i - 1]] || dp[i - 1][j];
21
        } else
22
          dp[i][j] = dp[i - 1][j];
23
      }
24
    }
25
    vector<int> v;
26
    for (int i = 0; i <= sum / 2; i++) {
27
      if (dp[n][i] == 1) v.push_back(i);
28
    }
29
    int mn = INT_MAX;
30
    for (int i = 0; i < v.size(); i++) {
31
      mn = min(mn, sum - 2 * v[i]);
32
    }
33
    return mn;
34
  }
35
};