คำอธิบายปัญหา
มีแท่งเหล็กหลายแท่ง สามารถเชื่อมต่อกันได้ ต้องการสร้างค้ำยัน 2 ด้านที่สูงเท่ากันที่สุด หาความสูงสูงสุด หากไม่ได้คืน 0
ตัวอย่าง
rods = [1,2,2,3,3,3,4] → Output: 9
Subset 1: [1,2,2,4] = 9, Subset 2: [3,3,3] = 9
แนวทางแก้ปัญหา: Dynamic Programming (Knapsack แบบความต่าง)
State: dp[i][diff] = ความสูงรวมสูงสุดของค้ำยันที่สั้นกว่า หลังพิจารณาแท่งแรก i แท่ง และความต่างระหว่างสองค้ำยันคือ diff
ใช้ offset 5000 เพื่อจัดการ diff ติดลบ (diff ∈ [-5000, 5000])
Transition สำหรับแท่งที่ i (ความยาว x):
- ไม่ใช้: dp[i+1][j] = max(dp[i+1][j], dp[i][j])
- ใส่ด้านที่สูงกว่า: diff เพิ่ม x → dp[i+1][j+x] = max(..., dp[i][j])
- ใส่ด้านที่สั้นกว่า: diff ลด x → dp[i+1][j-x] = max(..., dp[i][j] + x) (ความสูงสั้นกว่าเพิ่มขึ้น x)
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int tallestBillboard(vector<int>& rods) {
int n = rods.size();
const int N = 5000;
vector<vector<int>> dp(n+1, vector<int>(2*N+1, -1));
dp[0][N] = 0; // diff=0 at offset N
for(int i=0; i= 0) dp[i+1][j-x] = max(dp[i+1][j-x], dp[i][j] + x);
}
}
return dp[n][N];
}
};
ความซับซ้อน
- เวลา: O(n × sum) ~ O(20 × 5000) = O(10⁵)
- พื้นที่: O(n × sum) ~ O(10⁵)
