leetcode - knapsack dp

956. Tallest Billboard

1. Given an integer array, separate these numbers (don't have to use all numbers) into 2 sets, named A and B.
2. Sum(A) = Sum(B)
3. Find the maximum sum.

Note: The sum of rods is at most 5000.

Example:

(a) [1,2], max sum = 0.
(b) [1,2,3,4,5,6], max sum = 10, can separate into {2, 3, 5} and {4, 6}

12 ms version, sampled from committed solution:

// left/right is billboard height of each side
// index points to next rod
void dfs_12ms(vector<int> &rods, int left, int right,
              int remain, int index,
              int &result)
{
  if (abs(left - right) > remain ||
      left + right + remain <= result * 2)
    return;

  if (left == right && result < left)
    result = left;

  if (index == rods.size())
    return;

  remain -= rods[index];
  dfs_12ms(rods, left + rods[index], right, remain, index + 1, result);
  dfs_12ms(rods, left, right + rods[index], remain, index + 1, result);
  dfs_12ms(rods, left, right, remain, index + 1, result);
}

int tallestBillboard_12ms(vector<int> &rods) {
  sort(rods.begin(), rods.end(), greater<int>());
  int sum = 0;
  for (const auto &r : rods)
    sum += r;

  int result = 0;
  dfs_12ms(rods, 0, 0, sum, 0, result);
  return result;
}

// ref: https://leetcode.com/problems/tallest-billboard/discuss/203274/Simple-C%2B%2B-DP-beating-100-O(NM)#_=_
// 28 ms (CY 2nd attempt)
bool isValid(int s) const { return s >= 0; }

int tallestBillboard(vector<int>& rods) {
  if (rods.empty())
    return 0;

  int maxsum = accumulate(rods.begin(), rods.end(), 0) / 2;
  const int n = rods.size();
  
  // dp[i][diff]: The maximum pair of s0 and s1 from
  // set of {rods[j], j <= i} which has difference = diff
  //
  // s1 is always s0, so dp[i][diff] = s0 + diff = s1
  //vector<vector<int>> dp(n + 1, vector<int>(maxsum + 1));
  
  int dpPrevData[maxsum + 1];
  int dpCurData[maxsum + 1];
  
  int *dpPrev = dpPrevData;
  int *dpCur = dpCurData;
  
  for (int i = 1; i <= maxsum; i++)
    dpPrev[i] = -1;
  dpPrev[0] = 0;

  for (int i = 1; i <= n; ++i) {
    int rodi = rods[i - 1];
    for (int j = 0; j <= maxsum; ++j) {
      /// case a: Do not use rodi.
      int a = dpPrev[j];
      
      /// case b: Add rodi to s1.
      int b = -1;
      if (j >= rodi && isValid(dpPrev[j - rodi]))
        b = dpPrev[j - rodi] + rodi;
      
      /// case c: Add rodi to s0, but s1 is still greater than s0.
      int c = -1;
      if (j + rodi <= maxsum) // rodi > j )
        c = dpPrev[j + rodi];

      /// case d: Add rodi to s0, but s0 is now greater than s1,
      ///         and will be swapped.
      int d = -1;
      if (rodi > j && rodi - j <= maxsum && isValid(dpPrev[rodi - j]))
        d = dpPrev[rodi - j] + j;
      
      dpCur[j] = max({a, b, c, d});
    }
    swap(dpCur, dpPrev);
  }

  return dpPrev[0];
}