題目網址：https://leetcode.cn/problems/tallest-billboard/
題意：你正在安裝一個廣告牌, 並希望它高度最大。這塊廣告牌將有兩個鋼制支架, 兩邊各一個, 且每個鋼支架的高度必須相等。
你有一堆可以焊接在一起的鋼筋 rods, e.g. 如果鋼筋的長度為 1、2 和 3, 則可以將它們焊接在一起形成長度為 6 的支架。
返回廣告牌可能的最大安裝高度, 如果無法安裝廣告牌, 則返回 0。
Solution 1：(TLE 無法通過)
想法：利用 DP
1. 定義狀態：
- 首先, 會在
rods 前先加上一個 0, 代表什麼元素都沒有的狀態
dp[i][j][k]：rods[1:i] 中湊出左邊為 j、右邊為 k 是否可行
2. 得到轉移方程：
rods[i] 有「選 or 不選」兩種可能：
rods[i] 不選, 則 dp[i][j][k] = dp[i - 1][j][k]rods[i] 要選（rods[i] = h）：
- 將
rods[i] 加入左邊, 則 dp[i][j][k] = dp[i - 1][j - h][k]
- 將
rods[i] 加入右邊, 則 dp[i][j][k] = dp[i - 1][j][k - h]
3. 初始化：
dp[0][0][0]：當沒有元素時, 左邊為 0, 且右邊為 0 是可行的（什麼都不選）
➔ dp[0][0][0] = true
class Solution {
public:
int tallestBillboard(vector<int>& rods) {
const int n = rods.size();
const int sum = accumulate(rods.begin(), rods.end(), 0), half = sum / 2;
vector<vector<vector<bool>>> dp(n + 1, vector<vector<bool>>(half + 1, vector<bool>(half + 1, false)));
dp[0][0][0] = true;
rods.emplace(rods.begin(), 0);
for (int i = 1; i <= n; ++i) {
const int len = rods[i];
for (int j = 0; j <= half; ++j) {
for (int k = 0; k <= half; ++k) {
if (dp[i - 1][j][k]) {
dp[i][j][k] = true;
} else if (j >= len && dp[i - 1][j - len][k]) {
dp[i][j][k] = true;
} else if (k >= len && dp[i - 1][j][k - len]) {
dp[i][j][k] = true;
}
}
}
}
for (int j = sum / 2; j >= 0; --j) {
for (int k = sum / 2; k >= 0; --k) {
if (dp[n][j][k] && j == k) {
return j;
}
}
}
return 0;
}
};
|
- time：$O(n \cdot half^2)$ ➔ for loop
- space：$O(n \cdot half^2)$ ➔
dp
Solution 2：
想法：利用 DP
1. 定義狀態：
- 首先, 會在
rods 前先加上一個 0, 代表什麼元素都沒有的狀態
dp[i][j]：rods[1:i] 中湊出兩邊長度差為 j 時, 較短邊的最大長度
2. 得到轉移方程：
rods[i] 有「選 or 不選」兩種可能：
rods[i] 不選, 則 dp[i][j] = dp[i - 1][j]rods[i] 要選（rods[i] = h）：
將 rods[i] 加入短邊, 且加入後短邊長度仍小於長邊。若加入前的長度差為 j, 則加入後的差為 j - h, 且加入後較小邊的最大長度要加上 h
➔ dp[i][j - h] = dp[i - 1][j] + h
將 rods[i] 加入短邊, 且加入後短邊長度大於長邊。若加入前的長度差為 j, 則加入後的差為 h - j, 且加入後較小邊的最大長度要加上 j
➔ dp[i][h - j] = dp[i - 1][j] + j
將 rods[i] 加入長邊：加入前長度之差為 j, 則代表加入後的長度差為 j + h, 且加入後較短邊的最大長度不變
➔ dp[i][j + h] = dp[i - 1][j]
3. 初始化：
dp[0][0]：當沒有元素時, 左、右兩邊長度皆為 0, 此時長度差為 0, 較短邊的最大長度為 0
➔ dp[0][0] = 0- 其餘皆初始為
INT_MIN / 2, 代表還不知道較小邊的最大長度是多少（因為題目要求最大, 故初始值設小, 除 2 是因為怕操作時會 overflow）
class Solution {
public:
int tallestBillboard(vector<int>& rods) {
const int n = rods.size(), sum = accumulate(rods.begin(), rods.end(), 0);
vector<vector<int>> dp(n + 1, vector<int>(sum + 1, INT_MIN / 2));
dp[0][0] = 0;
rods.emplace(rods.begin(), 0);
for (int i = 1; i <= n; ++i) {
const int len = rods[i];
for (int j = 0; j <= sum; ++j) {
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
if (j >= len) {
dp[i][j - len] = max(dp[i][j - len], dp[i - 1][j] + len);
}
if (len >= j) {
dp[i][len - j] = max(dp[i][len - j], dp[i - 1][j] + j);
}
if (j + len <= sum) {
dp[i][j + len] = max(dp[i][j + len], dp[i - 1][j]);
}
}
}
return dp[n][0];
}
};
|
- time：$O(n \cdot sum)$ ➔ for loop
- space：$O(n \cdot sum)$ ➔
dp
Solution 3：
想法：改進 Solution 2, 由於 dp[i][j] 只會用到上一列的狀態, 因此只需保存上一列的狀態即可
class Solution {
public:
int tallestBillboard(vector<int>& rods) {
const int n = rods.size(), sum = accumulate(rods.begin(), rods.end(), 0);
vector<int> dp(sum + 1, INT_MIN / 2);
dp[0] = 0;
rods.emplace(rods.begin(), 0);
for (int i = 1; i <= n; ++i) {
const int len = rods[i];
const auto prevRow = dp;
for (int j = 0; j <= sum; ++j) {
dp[j] = max(dp[j], prevRow[j]);
if (j >= len) {
dp[j - len] = max(dp[j - len], prevRow[j] + len);
}
if (len >= j) {
dp[len - j] = max(dp[len - j], prevRow[j] + j);
}
if (j + len <= sum) {
dp[j + len] = max(dp[j + len], prevRow[j]);
}
}
}
return dp[0];
}
};
|
- time：$O(n \cdot sum)$ ➔ for loop
- space：$O(sum)$ ➔
dp
