Chọn nhà không kề nhau để được nhiều nhất
Một dãy nhà, mỗi nhà có một giá trị; không được lấy hai nhà liền kề. Đây là bài quy hoạch
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: python-basics, python-loop-basics, python-dp-climbing-stairs.
Nội dung đề bài
Mô tả bài toán
Một dãy nhà, mỗi nhà có một giá trị; không được lấy hai nhà liền kề. Đây là bài quy hoạch động có hai trạng thái rõ ràng: "lấy nhà đang xét" và "bỏ nhà đang xét". Chỉ cần giữ đúng hai con số đó là đủ, không cần mảng.
Yêu cầu
Viết hàm max_loot(values) trả về tổng lớn nhất của một tập nhà sao cho không có hai nhà nào kề nhau. Dãy rỗng cho 0.
Công thức truy hồi (đã kiểm tra bằng tay): gọi take là tổng tốt nhất khi LẤY nhà đang xét và skip là tổng tốt nhất khi BỎ nhà đang xét. Ban đầu take = skip = 0. Với mỗi value: take, skip = skip + value, max(take, skip); cuối cùng trả về max(take, skip).
Quy ước nộp bài
Nộp hàm max_loot trong solution.py. Hệ thống gọi hàm trực tiếp bằng tham số từ khoá values và so giá trị trả về với kết quả đã cho; không đọc stdin và không in ra stdout.
Input
- values: danh sách giá trị của từng nhà, số nguyên không âm, độ dài từ 0 đến 20.
Output
Một số nguyên là tổng lớn nhất lấy được.
Ràng buộc
- Không được lấy hai nhà liền kề; có thể bỏ bao nhiêu nhà tuỳ ý.
- Không phải mọi nhà đều nằm trên một chuỗi bắt đầu từ nhà đầu tiên, nên [2, 1, 1, 2]
phải cho 4 chứ không phải 3.
- Dãy rỗng trả về 0; nhà một phần tử trả về chính giá trị đó.
Ví dụ 1
Input
max_loot(values=[2, 7, 9, 3, 1])
Output
12
Ví dụ 2
Input
max_loot(values=[5])
Output
5
Giải thích
Với values = [2, 7, 9, 3, 1], chọn nhà thứ nhất, thứ ba và thứ năm: 2 + 9 + 1 = 12, nên hàm trả về 12. Với values = [2, 1, 1, 2], chọn nhà đầu và nhà cuối được 4 — nhiều hơn cách chọn hai nhà giữa (1 + 1 = 2).
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
