文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

你正在安裝一個廣告牌，并希望它高度最大。
這塊廣告牌將有兩個鋼制支架，兩邊各一個。每個鋼支架的高度必須相等。

你有一堆可以焊接在一起的鋼筋 rods。
舉個例子，如果鋼筋的長度為 1、2 和 3，則可以將它們焊接在一起形成長度為 6 的支架。

返回廣告牌的最大可能安裝高度。如果沒法安裝廣告牌，請返回 0。

示例 1： 輸入：[1,2,3,6] 輸出：6 解釋：我們有兩個不相交的子集 {1,2,3} 和 {6}，它們具有相同的和 sum = 6。示例 2： 輸入：[1,2,3,4,5,6] 輸出：10 解釋：我們有兩個不相交的子集 {2,3,5} 和 {4,6}，它們具有相同的和 sum = 10。示例 3： 輸入：[1,2] 輸出：0 解釋：沒法安裝廣告牌，所以返回 0。提示： 0 <= rods.length <= 20 1 <= rods[i] <= 1000 鋼筋的長度總和最多為 5000

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/tallest-billboard
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

2. 解題

• dp[i][j] 表示處理完 i 鋼筋，兩邊差距為 j 時，可以組成的最大高度

class Solution { public:int tallestBillboard(vector<int>& rods) {if(rods.size() <= 1)return 0;int dp[20][5001], n = rods.size();int total = accumulate(rods.begin(), rods.end(), 0);// dp[i][j] 表示處理完 i 支架，兩邊差距為 j 時，可以組成的最大高度memset(dp, -1, sizeof(dp));dp[0][rods[0]] = dp[0][0] = 0;for(int i = 1; i < rods.size(); i++) { //樣本維度for(int j = 0; j <= total; ++j){if(dp[i-1][j] == -1)//上一行狀態(tài)不存在continue;// 當前鋼筋不要，丟棄dp[i][j] = max(dp[i][j], dp[i-1][j]);// 當前鋼筋，加在長的一邊dp[i][j+rods[i]] = max(dp[i][j+rods[i]], dp[i-1][j]);// 當前鋼筋，加在短的一邊，現(xiàn)在高度差為 abs(j-rods[i])dp[i][abs(j-rods[i])] = max(dp[i][abs(j-rods[i])], dp[i-1][j]+min(j, rods[i]));}}// 返回高度差為 0 的情況return dp[n-1][0]==-1 ? 0 : dp[n-1][0];} };

40 ms 8.1 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 956. 最高的广告牌（DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。