Skip to content

956. Tallest Billboard 👍

Approach 1: 2D DP

  • Time: $O(n \cdot \texttt{sum})$, where $\texttt{sum} = \Sigma |\texttt{rods[i]}|$
  • Space: $O(n \cdot \texttt{sum})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  int tallestBillboard(vector<int>& rods) {
    const int n = rods.size();
    const int sum = accumulate(rods.begin(), rods.end(), 0);
    // dp[i][j] := the maximum min-height of using rods[0..i) to pile two piles
    // that have height difference j
    vector<vector<int>> dp(n + 1, vector<int>(sum + 1, -1));
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
      const int h = rods[i - 1];
      for (int j = 0; j <= sum - h; ++j) {
        if (dp[i - 1][j] < 0)
          continue;
        // Don't use rods[i - 1].
        dp[i][j] = max(dp[i][j], dp[i - 1][j]);
        // Put on the taller pile.
        dp[i][j + h] = max(dp[i][j + h], dp[i - 1][j]);
        // Put on the shorter pile.
        dp[i][abs(j - h)] = max(dp[i][abs(j - h)], dp[i - 1][j] + min(j, h));
      }
    }

    return dp[n][0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public int tallestBillboard(int[] rods) {
    final int n = rods.length;
    final int sum = Arrays.stream(rods).sum();
    // dp[i][j] := the maximum min-height of using rods[0..i) to pile two piles
    // that have height difference j
    int[][] dp = new int[n + 1][sum + 1];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, -1));
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
      final int h = rods[i - 1];
      for (int j = 0; j <= sum - h; ++j) {
        if (dp[i - 1][j] < 0)
          continue;
        // Don't use rods[i - 1].
        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
        // Put on the taller pile.
        dp[i][j + h] = Math.max(dp[i][j + h], dp[i - 1][j]);
        // Put on the shorter pile.
        dp[i][Math.abs(j - h)] = Math.max(dp[i][Math.abs(j - h)], dp[i - 1][j] + Math.min(j, h));
      }
    }

    return dp[n][0];
  }
}

Approach 2: 1D DP

  • Time: $O(n \cdot \texttt{sum})$
  • Space: $O(\texttt{sum})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int tallestBillboard(vector<int>& rods) {
    const int sum = accumulate(rods.begin(), rods.end(), 0);
    // dp[i] := the maximum min-height of using rods so far to pile two piles
    // that have height difference i
    vector<int> dp(sum + 1, -1);
    dp[0] = 0;

    for (const int h : rods) {
      vector<int> prev(dp);
      for (int i = 0; i <= sum - h; ++i) {
        if (prev[i] < 0)
          continue;
        // Don't use this rod.
        dp[i] = max(dp[i], prev[i]);
        // Put on the taller pile.
        dp[i + h] = max(dp[i + h], prev[i]);
        // Put on the shorter pile.
        dp[abs(i - h)] = max(dp[abs(i - h)], prev[i] + min(i, h));
      }
    }

    return dp[0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int tallestBillboard(int[] rods) {
    final int sum = Arrays.stream(rods).sum();
    // dp[i] := the maximum min-height of using rods so far to pile two piles
    // that have height difference i
    int[] dp = new int[sum + 1];
    Arrays.fill(dp, -1);
    dp[0] = 0;

    for (final int h : rods) {
      int[] prev = dp.clone();
      for (int i = 0; i <= sum - h; ++i) {
        if (prev[i] < 0)
          continue;
        // Don't use this rod.
        dp[i] = Math.max(dp[i], prev[i]);
        // Put on the taller pile.
        dp[i + h] = Math.max(dp[i + h], prev[i]);
        // Put on the shorter pile.
        dp[Math.abs(i - h)] = Math.max(dp[Math.abs(i - h)], prev[i] + Math.min(i, h));
      }
    }

    return dp[0];
  }
}