House Robber
Những ngôi nhà nằm thành một hàng dọc theo con phố, và nums[i] là số tiền trong ngôi nhà i. Bạn có thể lấy tiền từ bất kỳ ngôi nhà nào mình chọn, nhưng không được lấy tiền từ hai ngôi nhà nằm cạnh nhau. Hãy trả về tổng số tiền lớn nhất bạn có thể lấy.
Hàm
- numsinteger-array
- tiền trong mỗi ngôi nhà, theo thứ tự trên phố
- Trả vềinteger
- tổng lớn nhất bạn có thể lấy mà không lấy từ hai ngôi nhà liền kề
Ràng buộc
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 1000- Đáp án tối đa là
5 × 106, nên vừa với một số nguyên có dấu 32 bit.
Ví dụ
- Đầu vào
- nums = [5, 3, 4, 11, 2]
- Đầu ra
- 16
- Giải thích
- Lấy 5 và 11 từ nhà số 0 và số 3 để được 16. Bạn có thể bỏ qua hai ngôi nhà liên tiếp, và cách này hiệu quả hơn mọi phương án khác: 5 + 4 + 2 = 11 và 3 + 11 = 14.
- Đầu vào
- nums = [3, 10, 3]
- Đầu ra
- 10
- Giải thích
- Hai ngôi nhà ở hai đầu cộng lại được 3 + 3 = 6. Riêng ngôi nhà ở giữa có giá trị 10, nhưng chọn ngôi nhà này thì không thể chọn cả hai ngôi nhà bên cạnh.
- Đầu vào
- nums = [2, 9, 3, 1, 8]
- Đầu ra
- 17
- Giải thích
- 9 và 8 nằm trong các ngôi nhà số 1 và 4, không nằm cạnh nhau, nên tổng là 17. Nếu lấy cách một ngôi nhà, bắt đầu từ đầu, ta chỉ có 2 + 3 + 8 = 13.
Câu hỏi mở rộng
Trả về các ngôi nhà cần lấy cùng với tổng số. Bạn cần giữ lại những gì từ bảng để dựng lại danh sách đó, và liệu hai tổng đang chạy có làm được việc này không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Hãy xem ngôi nhà cuối cùng. Một phương án chọn ngôi nhà đó hoặc bỏ qua nó. Mỗi lựa chọn để lại cho bạn bài toán nào cần giải?
Nếu bạn bỏ qua ngôi nhà
k-1, kết quả tốt nhất là kết quả tốt nhất trongk-1ngôi nhà đầu tiên. Nếu bạn chọn ngôi nhà đó, bạn cộngnums[k-1]vào kết quả tốt nhất trongk-2ngôi nhà đầu tiên. Đáp án chokngôi nhà là giá trị lớn hơn trong hai kết quả.Điền các tổng lớn nhất đó, tính từ đầu con phố, bắt đầu bằng 0 khi chưa có ngôi nhà nào. Mỗi tổng chỉ cần hai tổng trước đó, nên chỉ cần hai biến.
Lời giải
Các cách làm tắt đều thất bại: chọn cách nhà cách một nhà sẽ bỏ lỡ 5 và 11 trong [5, 3, 4, 11, 2], còn chọn căn nhà giàu nhất trước sẽ cho kết quả kém hơn với [3, 4, 3]. Thay vào đó, hãy quyết định từng căn nhà một: tổng lớn nhất tính đến một căn nhà chỉ phụ thuộc vào hai tổng lớn nhất tính đến hai căn nhà trước đó.
Thử cả hai lựa chọn ở mỗi ngôi nhà
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Mỗi phương án hoặc bỏ qua ngôi nhà cuối cùng, hoặc chọn ngôi nhà đó. Bỏ qua ngôi nhà cuối cùng thì phương án tốt nhất chỉ xét n-1 ngôi nhà đầu tiên; chọn ngôi nhà đó thì cộng nums[n-1] vào phương án tốt nhất chỉ xét n-2 ngôi nhà đầu tiên. Vì vậy, most(k) = max(most(k-1), most(k-2) + nums[k-1]), với most(0) = 0 và most(1) = nums[0]. Hai nhánh bao quát mọi phương án, nên đáp án là chính xác.
Hai nhánh chồng lặp: most(k-1) lại cần tính most(k-2), và số lần gọi tăng theo dãy Fibonacci, xấp xỉ 1.6^n. Với 40 ngôi nhà, cần hơn 300 triệu lần gọi, trong khi n có thể đạt 10^4.
Thuật toán
- Viết hàm trợ giúp
most(k)trả về số tiền lớn nhất bạn có thể lấy từkngôi nhà đầu tiên. - Trả về 0 khi
kbằng 0, vànums[0]khikbằng 1. - Nếu không, hãy tính
skip = most(k-1)vàtake = most(k-2) + nums[k-1]. - Trả về giá trị lớn hơn trong hai giá trị đó. Đáp án là
most(n).
def rob(nums):
def most(k):
# The most you can take from the first k houses
if k == 0:
return 0
if k == 1:
return nums[0]
# Skip house k-1, or take it and skip house k-2
return max(most(k - 1), most(k - 2) + nums[k - 1])
return most(len(nums))Bảng từ dưới lên
Ý tưởng
Phép đệ quy chỉ hỏi về most(0) đến most(n): n + 1 câu hỏi. Trả lời mỗi câu hỏi một lần trong bảng best, bắt đầu từ best[0] = 0 và best[1] = nums[0], rồi điền từ dưới lên, bắt đầu với k = 2, để hai giá trị mà mỗi câu trả lời đọc đã có sẵn.
Với [5, 3, 4, 11, 2], bảng là 0, 5, 5, 9, 16, 16. Tại k = 4, bỏ qua ngôi nhà thứ 3 giữ nguyên best[3] = 9, còn lấy 11 cộng với best[2] = 5 cho kết quả 16, lớn hơn. Mỗi giá trị cần một phép so sánh: thời gian O(n) và không gian O(n).
Thuật toán
- Tạo một bảng
bestcó n + 1 phần tử. - Đặt
best[0] = 0vàbest[1] = nums[0]. - Với
ktừ 2 đến n, đặtbest[k]bằng giá trị lớn hơn giữabest[k-1]vàbest[k-2] + nums[k-1]. - Trả về
best[n].
def rob(nums):
n = len(nums)
# best[k] is the most you can take from the first k houses
best = [0] * (n + 1)
best[1] = nums[0]
for k in range(2, n + 1):
# Skip house k-1, or take it on top of the best from the first k-2 houses
best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
return best[n]Hai tổng đang chạy
Ý tưởng
Mỗi phần tử chỉ đọc hai phần tử đứng trước nó, nên hãy giữ lại hai số thay vì cả bảng: twoBack và oneBack, tổng tốt nhất tính đến căn nhà cách đó hai căn và căn nhà ngay trước đó. Với một căn nhà có x, tổng tốt nhất mới là max(oneBack, twoBack + x); sau đó cập nhật cả hai giá trị. Cả hai đều bắt đầu bằng 0, tương ứng với con phố trống trước căn nhà đầu tiên, nên không cần xử lý riêng trường hợp con phố chỉ có một căn nhà. Thời gian vẫn là O(n), còn bộ nhớ giảm xuống O(1).
Thuật toán
- Đặt
twoBackvàoneBackthành 0. - Với mỗi giá trị
xtrongnums, tínhcurrent = max(oneBack, twoBack + x). - Chuyển
oneBackvàotwoBack, sau đó chuyểncurrentvàooneBack. - Sau căn nhà cuối cùng, trả về
oneBack.
def rob(nums):
# The best totals from the houses up to two back and up to one back
two_back, one_back = 0, 0
for amount in nums:
# Skip this house, or take it on top of the best from two back
two_back, one_back = one_back, max(one_back, two_back + amount)
return one_back
Lỗi thường gặp và trường hợp biên
- Ghi đè
oneBacktrước khi sao chép nó vàotwoBack. Ngôi nhà tiếp theo sẽ đọc tổng sai. Hãy tính giá trị tốt nhất mới trước, rồi mới dịch chuyển, hoặc gán cả hai cùng lúc. - Đọc
nums[1], hoặc gán trướcbest[1]vàbest[2]. Cả hai cách đều gây lỗi khi con phố chỉ có một ngôi nhà, chẳng hạn như[0]. - Trong Lua và R, mảng bắt đầu từ chỉ số 1, nên số tiền trong ngôi nhà
k-1nằm ởnums[k].
Câu hỏi thường gặp3
Độ phức tạp thời gian và không gian của House Robber là bao nhiêu?
Quy hoạch động xét mỗi ngôi nhà một lần, nên mất thời gian O(n). Bảng đầy đủ dùng O(n) không gian, còn chỉ giữ lại hai tổng gần nhất thì giảm xuống O(1). Đệ quy thông thường không lưu đáp án sẽ thực hiện khoảng 1.6^n lời gọi.
Tại sao lấy cách nhà lại không giải được bài toán Kẻ trộm nhà?
Đôi khi, kế hoạch tốt nhất bỏ qua hai ngôi nhà liên tiếp. Trong [10, 1, 1, 10], tổng tiền ở các ngôi nhà chẵn và các ngôi nhà lẻ đều bằng 11, trong khi ngôi nhà đầu tiên và ngôi nhà cuối cùng có tổng là 20.
Làm thế nào để giải bài toán Kẻ trộm nhà khi các ngôi nhà xếp thành một vòng tròn?
Trong một vòng tròn, ngôi nhà đầu tiên và ngôi nhà cuối cùng là hàng xóm của nhau, vì vậy một kế hoạch chỉ lấy tối đa một trong hai ngôi nhà đó. Chạy lời giải cho con phố thẳng hai lần, một lần không có ngôi nhà cuối cùng và một lần không có ngôi nhà đầu tiên, rồi trả về kết quả lớn hơn. Trường hợp chỉ có một ngôi nhà là trường hợp đặc biệt: đáp án chính là ngôi nhà đó.
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 rob(nums):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
nums = [5, 3, 4, 11, 2]
Đầu ra mong đợi
16