Burst Balloons
Một dãy bóng bay được cho dưới dạng nums, trong đó nums[i] là số ghi trên quả bóng thứ i. Bạn làm nổ tất cả bóng, từng quả một, theo thứ tự bất kỳ. Làm nổ một quả bóng giúp bạn kiếm được left × nums[i] × right xu, trong đó left và right là các số ghi trên hai quả bóng hiện là hàng xóm của nó, tức là những quả bóng gần nhất ở mỗi bên vẫn còn trong dãy. Nếu không có hàng xóm ở một bên, giá trị ở bên đó được tính là 1. Sau khi một quả bóng nổ, hai quả bóng hàng xóm của nó trở thành hàng xóm của nhau. Hãy trả về số xu tối đa bạn có thể kiếm được.
Hàm
- numsinteger-array
- các số trên những quả bóng bay, từ trái sang phải
- Trả vềinteger
- số xu nhiều nhất bạn có thể thu thập bằng cách làm nổ mọi quả bóng bay
Ràng buộc
1 ≤ nums.length ≤ 3000 ≤ nums[i] ≤ 100- Đáp án nhỏ hơn 3 × 108 nên nằm trong phạm vi của số nguyên có dấu 32 bit.
Ví dụ
- Đầu vào
- nums = [2, 4, 3]
- Đầu ra
- 33
- Giải thích
- Cho nổ số 4 để được 2 × 4 × 3 = 24. Số 2, giờ nằm cạnh số 3, được 1 × 2 × 3 = 6, còn số 3 được 3: tổng cộng là 33.
- Đầu vào
- nums = [6, 1, 2, 5]
- Đầu ra
- 108
- Giải thích
- Làm nổ số 1 (6 × 1 × 2 = 12), rồi đến số 2, lúc này nằm giữa 6 và 5 (6 × 2 × 5 = 60), sau đó đến số 5 được 30 và số 6 được 6: tổng cộng là 108.
- Đầu vào
- nums = [8]
- Đầu ra
- 8
- Giải thích
- Quả bóng duy nhất không có bóng nào bên cạnh, và mỗi quả bóng bên cạnh bị thiếu được tính là 1, nên quả bóng này được 1 × 8 × 1 = 8 điểm.
Câu hỏi mở rộng
Bạn cũng có thể trả về một đơn hàng bùng nổ mang lại nhiều xu nhất không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Giả sử bạn quyết định xem nên làm nổ quả bóng nào trước. Hai quả bóng bên cạnh nó sẽ trở thành hai quả bóng liền kề, vì vậy các quả bóng bên trái và bên phải vẫn ảnh hưởng lẫn nhau. Bạn có thể chia bài toán thành hai bài toán nhỏ hơn theo cách đó không?
Hãy suy nghĩ ngược lại và chọn quả bóng bay bị nổ cuối cùng trong một đoạn. Trước đó, nó vẫn đứng yên như một bức tường, nên những quả bóng bay bên trái và bên phải nó không bao giờ trở thành hàng xóm. Khi nó cuối cùng bị nổ, hàng xóm của nó chính là hai quả bóng bay nằm ở hai đầu đoạn.
Thêm số 1 vào cả hai đầu của
nums. Gọibest[left][right]là số xu nhiều nhất có thể nhận được từ những quả bóng nằm giữa vị tríleftvàright. Thử từng quả bóngkở giữa làm quả cuối cùng: quả bóng đó mang lạibest[left][k] + best[k][right]xu, cộng vớivals[left] × vals[k] × vals[right]. Tính các khoảng ngắn trước, rồi đến các khoảng dài.
Lời giải
Mỗi lần làm nổ một quả bóng, thứ tự các quả bóng đứng cạnh nhau thay đổi, vì vậy quả bóng bạn làm nổ đầu tiên không chia hàng thành hai phần: hai quả bóng ở hai bên trở thành hàng xóm. Quả bóng cuối cùng bị làm nổ trong một đoạn mới là quả bóng chia hàng. Nó vẫn còn đó khi mọi quả bóng khác đã biến mất, nên các đoạn ở hai bên của nó độc lập với nhau, và bảng khoảng trên các đoạn sẽ giải bài toán trong O(n³).
Hãy thử mọi thứ tự nổ
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Chọn một quả bóng, ghi nhận left × value × right, loại bỏ nó rồi giải hàng ngắn hơn theo cách tương tự, đồng thời giữ lại tổng lớn nhất trong mọi lựa chọn. Cách này thử mọi thứ tự nên cho kết quả chính xác.
Lần nổ đầu tiên có n lựa chọn, lần tiếp theo có n-1 lựa chọn, cứ thế tiếp tục: có n! thứ tự, riêng với 12 quả bóng đã có 479,001,600 thứ tự. Ghi nhớ kết quả cho mỗi tập hợp các quả bóng còn lại không giúp ích, vì có 2^n tập hợp.
Thuật toán
- Viết hàm (function)
burstAll(row)để tính số xu tối đa nhận được từ các quả bóng trongrow, trả về 0 nếu hàng trống. - Với mỗi vị trí
k, nhậnleft × row[k] × rightxu, dùng 1 ở phía ngoài mỗi đầu hàng, rồi cộng số xu từburstAllcủa hàng sau khi bỏrow[k]. - Trả về tổng lớn nhất trong tất cả các vị trí
k, rồi gọiburstAll(nums).
def maxCoins(nums):
# Most coins you can still collect from the balloons in row
def burst_all(row):
top = 0
for k in range(len(row)):
left = row[k - 1] if k > 0 else 1
right = row[k + 1] if k + 1 < len(row) else 1
# Burst row[k] now, then do as well as possible with the rest
coins = left * row[k] * right + burst_all(row[:k] + row[k + 1:])
top = max(top, coins)
return top
return burst_all(nums)Đệ quy với quả bóng cuối cùng, kèm bộ nhớ đệm
Ý tưởng
Thêm một số 1 ở mỗi đầu hàng: vals = [1] + nums + [1]. Các số đệm không bao giờ vỡ và thay cho những quả bóng lân cận bị thiếu. Gọi solve(left, right) là số xu tối đa có thể nhận được từ những quả bóng nằm hẳn giữa hai vị trí còn đứng.
Giả sử k là quả bóng cuối cùng vỡ trong khoảng đó. Mọi quả bóng khác trong khoảng đều vỡ khi k vẫn đứng như một bức tường, vì vậy phần giữa left và k chỉ có những quả bóng của riêng nó cùng hai biên cố định, phần giữa k và right cũng vậy. Khi k vỡ, hai quả bóng lân cận của nó chính là left và right. Vì vậy, kết quả tốt nhất cho khoảng đó là giá trị tốt nhất trong mọi trường hợp k, bằng tổng kết quả tốt nhất của hai phần cộng với vals[left] × vals[k] × vals[right]. Đáp án là khoảng giữa hai số đệm. Có khoảng n²/2 khoảng, mỗi khoảng thử tối đa n quả bóng, nên dùng bộ nhớ đệm sẽ giảm độ phức tạp còn O(n³).
Thuật toán
- Tạo
valstừnums, thêm số 1 vào mỗi đầu, rồi đặtmbằng độ dài của nó. - Tạo một mảng ghi nhớ
m × mchứa toàn số -1. - Viết
solve(left, right): trả về 0 nếuright - left < 2, và trả về giá trị đã lưu nếu có. - Nếu không, thử mọi
knằm строго giữa chúng làm quả bóng cuối cùng, giữ lại giá trị lớn nhất củasolve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right], rồi lưu giá trị đó. - Trả về
solve(0, m-1).
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
memo = [[-1] * m for _ in range(m)]
# Most coins from the balloons strictly between left and right
def solve(left, right):
if right - left < 2:
return 0
if memo[left][right] >= 0:
return memo[left][right]
top = 0
for last in range(left + 1, right):
# last bursts after every other balloon in the gap
coins = solve(left, last) + solve(last, right) + vals[left] * vals[last] * vals[right]
top = max(top, coins)
memo[left][right] = top
return top
return solve(0, m - 1)Điền vào bảng khoảng theo chiều rộng
Ý tưởng
Đệ quy chỉ xét các khoảng hẹp hơn, vì vậy hãy điền cùng một bảng bằng các vòng lặp, từ khoảng hẹp đến khoảng rộng. Khi cần đến một khoảng rộng hơn, best[left][k] và best[k][right] đã có giá trị cuối cùng.
Với [2, 4, 3], sau khi thêm phần đệm thành [1, 2, 4, 3, 1], best[0][4] thử từng quả bóng bay làm quả cuối cùng. Nếu quả bóng bay số 3 là quả cuối cùng, ta có best[0][3] = 30 cộng với 1 × 3 × 1, bằng 33, là kết quả tốt nhất trong ba khả năng.
Lượng công việc vẫn như phiên bản dùng memo, nhưng các vòng lặp thông thường bỏ qua hàng triệu lần gọi hàm, giúp phiên bản này nhanh hơn vài lần trong những ngôn ngữ như Python hoặc R.
Thuật toán
- Tạo
valstừnums, thêm số 1 vào mỗi đầu, rồi đặtmbằng độ dài của nó. - Tạo bảng
bestkích thướcm × m, điền giá trị 0. - Với mỗi độ rộng từ 2 đến
m-1, và mỗileftsao choright = left + widthnằm trong mảng, thử mọiknằm строго giữa chúng. - Đặt
best[left][right]bằng giá trị lớn nhất trongbest[left][k] + best[k][right] + vals[left] × vals[k] × vals[right]. - Trả về
best[0][m-1].
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
# best[left][right]: most coins from the balloons strictly between left and right
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
edge = vals[left] * vals[right]
top = 0
for last in range(left + 1, right):
# last goes after every other balloon in the gap,
# so left and right are its neighbours when it bursts
coins = best[left][last] + best[last][right] + edge * vals[last]
if coins > top:
top = coins
best[left][right] = top
return best[0][m - 1]
Lỗi thường gặp và trường hợp biên
- Tách ở quả bóng nổ đầu tiên, dùng hai quả bóng liền kề ban đầu,
nums[k-1] × nums[k] × nums[k+1], cộng với giá trị của hai phần hai bên. Những quả bóng liền kề đó có thể đã biến mất: với[2, 4, 3], cách này cho kết quả 44, cao hơn mọi kết quả thực tế có thể đạt được. - Điền bảng theo từng hàng, tăng dần
left. Khi đóbest[k][right]vớik > leftchưa được tính và có giá trị 0. Hãy điền theo độ rộng hoặc duyệtlefttheo thứ tự giảm dần. - Đánh dấu khoảng chưa giải trong bộ nhớ memo bằng 0. Khoảng gồm các quả bóng có giá trị 0 thực sự có giá trị 0, nên sẽ được giải lại mỗi lần duyệt đến. Hãy dùng -1.
- Trong Lua và R, các vị trí đệm bắt đầu từ 1 và kết thúc ở
m, vì vậy đáp án làbest[1][m].
Câu hỏi thường gặp3
Tại sao Burst Balloons chọn quả bóng bay cuối cùng thay vì quả đầu tiên?
Sau đợt nổ đầu tiên, hai quả bóng ở hai bên trở thành hàng xóm của nhau nên vẫn ảnh hưởng lẫn nhau. Quả bóng cuối cùng trong một đoạn vẫn còn khi những quả khác nổ, nên hai bên của nó không bao giờ gặp nhau và mỗi bên là một bài toán con độc lập. Khi quả bóng đó nổ, các quả bóng hàng xóm của nó trở thành hai đầu đoạn.
Độ phức tạp thời gian của bài toán Burst Balloons là gì?
Tốn thời gian O(n³) và bộ nhớ O(n²): có khoảng n²/2 khoảng trống, mỗi khoảng thử tối đa n quả bóng làm quả cuối cùng. Với 300 quả bóng, số bước vào khoảng 4.5 × 10^6. Thử mọi thứ tự có độ phức tạp O(n · n!).
Liệu có thể giải bài toán nổ bóng bay bằng cách chọn thứ tự tham lam không?
Không. Làm nổ quả bóng nhỏ nhất trước sẽ được 24 với [2, 4, 3], trong khi có thể đạt 33. Làm nổ quả bóng đem lại nhiều điểm nhất ở thời điểm hiện tại sẽ được 42 với [2, 9, 2], trong khi làm nổ quả bóng có giá trị 2 trước sẽ được 18 + 18 + 9 = 45. Mỗi lần làm nổ bóng sẽ thay đổi giá trị của những quả bóng tiếp theo.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def maxCoins(nums):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
nums = [2, 4, 3]
Đầu ra mong đợi
33