มีรายการสตริงประกอบ 'A' และ 'B' และค่า a, b หาจำนวนสตริงสูงสุดที่สร้างได้ ใช้ A ได้สูงสุด a ตัว B ได้สูงสุด b ตัว ไม่ซ้ำ
เช่น strings=["AAABB","AABB","AA","BB"], a=4, b=2 ให้ 2 เลือก ["AABB","AA"]
ขั้นตอนการแก้ปัญหา
- แปลงแต่ละสตริงเป็นคู่ (จำนวน A, จำนวน B)
- DP แบบ 0/1 Knapsack:
ans[(a,b)] = จำนวนสูงสุด - สำหรับแต่ละคู่ (A,B) อัปเดตสถานะที่เป็นไปได้
- คืนค่าสูงสุดใน ans
ตัวอย่างโค้ด
class Solution:
def solve(self, strings, a, b):
pairs = []
for w in strings:
A = w.count("A")
B = len(w) - A
pairs.append((A,B))
ans = {(a,b): 0}
for A,B in pairs:
temp = dict(ans)
for (ta,tb), wc in ans.items():
if ta>=A and tb>=B:
rem = (ta-A, tb-B)
temp[rem] = max(temp.get(rem,0), wc+1)
ans = temp
return max(ans.values())
ob = Solution()
strings = ["AAABB","AABB","AA","BB"]
a = 4; b = 2
print(ob.solve(strings, a, b))
อินพุต
["AAABB","AABB","AA","BB"], 4, 2
เอาต์พุต
2
