956.最高的广告牌

最高的广告牌

你正在安装一个广告牌，有两个等高的钢制支架。你有一堆钢筋，可以焊接在一起形成特定长度。返回能形成的最高广告牌高度。

示例 1:

输入：rods = [1, 2, 3, 6]
输出：6

示例 2:

输入：rods = [1, 2, 3, 4, 5, 6]
输出：10

提示:

• 1 <= rods.length <= 20
• 1 <= rods[i] <= 1000

解析

使用哈希表存储每个可能的差值对应的最大较小值。dp[diff] = max(较小值)。

var tallestBillboard = function (rods) {
  const dp = { 0: 0 };

  for (const x of rods) {
    const cur = Object.assign({}, dp);
    for (const [diff, smaller] of Object.entries(dp)) {
      const larger = smaller + diff;
      cur[diff + x] = Math.max(cur[diff + x] || 0, smaller);
      const newDiff = Math.abs(larger - (smaller + x));
      cur[newDiff] = Math.max(cur[newDiff] || 0, Math.min(larger, smaller + x));
    }
    dp = cur;
  }

  return dp[0];
};

时间复杂度 O(n * M)，空间复杂度 O(M)，其中 M 是可能的状态数。