Bạn là một tên trộm lên kế hoạch trộm các ngôi nhà dọc theo một con phố. Mỗi ngôi nhà có một lượng tiền nhất định. Các ngôi nhà có hệ thống báo động kết nối: nếu hai ngôi nhà liền kề nhau bị đột nhập trong cùng một đêm, chuông báo động sẽ tự động reo.
Cho mảng số nguyên nums biểu thị số tiền của mỗi ngôi nhà. Hãy tính số tiền tối đa bạn có thể trộm được đêm nay mà không làm chuông báo động reo.
Ví dụ 1:
Input: nums = [1, 2, 3, 1]
Output: 4
Giải thích: Trộm nhà 1 (tiền = 1) và nhà 3 (tiền = 3). Tổng = 4.Ví dụ 2:
Input: nums = [2, 7, 9, 3, 1]
Output: 12
Giải thích: Trộm nhà 1 (2), nhà 3 (9) và nhà 5 (1). Tổng = 12.Định Dạng Đầu Vào (Input)
Một dòng chứa mảng số nguyên nums
Định Dạng Đầu Ra (Output)
Một số nguyên duy nhất là số tiền tối đa có thể trộm
Ràng Buộc (Constraints)
1 <= nums.length <= 1000 <= nums[i] <= 400
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[1, 2, 3, 1]
Output:
4
Giải thích: Trộm 1 + 3 = 4
Ví dụ 2:
Input:
[2, 7, 9, 3, 1]
Output:
12
Giải thích: Trộm 2 + 9 + 1 = 12
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Quy Hoạch Động Tuyến Tính O(n)
Tại nhà i, có 2 lựa chọn:
1. Trộm nhà i: Số tiền = nums[i] + max_tien(i - 2)
2. Bỏ qua nhà i: Số tiền = max_tien(i - 1)
Công thức: dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
Dữ liệu đầu vào (Input):
[1, 2, 3, 1]
Kết quả kỳ vọng (Expected Output):
4
Dữ liệu đầu vào (Input):
[2, 7, 9, 3, 1]
Kết quả kỳ vọng (Expected Output):
12
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
