198. House Robber
Tags:
Medium
Skills:
DP
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu: Cho một mảng số nguyên nums, mỗi phần tử đại diện cho số tiền ở mỗi căn nhà. Bạn không được trộm hai căn nhà liền kề. Hãy trả về tổng số tiền lớn nhất có thể trộm được mà không báo động cảnh sát
Phân tích
- Với mỗi căn nhà, bạn có hai lựa chọn
- Trộm nhà này:
- Bạn cộng số tiền ở nhà này với tổng tiền trộm được đến nhà cách đó 2 căn
- Không trộm nhà này:
- Tổng tiền là tổng lớn nhất đến nhà trước đó
- Bài toán có tính chất DP vì kết quả tối ưu ở mỗi bước phụ thuộc vào các bước trước đó
Công thức DP
Solution - DP
typescripttypescript
1function rob(nums: number[]): number {
2 if (nums.length === 0) return 0
3 if (nums.length === 1) return nums[0];
4
5 const dp: number[] = [];
6 dp[0] = nums[0];
7 dp[1] = Math.max(nums[0], nums[1]);
8
9 for (let i = 2; i < nums.length; i++) {
10 dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
11 }
12 return dp[nums.length - 1]
13};💡
Deep dive
- dp[i - 1]: Không lấy nhà i, giữ nguyên kết quả tốt nhất đến nhà i - 1
- dp[i - 2] + nums[i]: Lấy nhà i, cộng tiền nhà i với kết quả tốt nhất đến nhà i - 2 (vì phải bỏ nhà i - 1)
- dp[i -2] nghĩa là mình sẽ bỏ qua i - 1 vì nó liền kề và cộng thêm num xem có lớn hơn i -1 không
Ở mỗi bước bạn chỉ cần chọn phương án tốt nhất giữa hai lựa chọn này
Solution - Optimize
typescripttypescript
1function rob(nums: number[]): number {
2 let prev1 = 0 // dp[i - 1]
3 let prev2 = 0 // dp[i - 2]
4 for(const num of nums) {
5 const temp = prev1;
6 prev1 = Math.max(prev1, prev2 + num);
7 prev2 = temp;
8 }
9 return prev1
10};💡
Tóm tắt
- prev1: tổng tiền tối đa lấy được đến nhà trước đó
- prev2: Tổng tiền tối đa lấy được đến nhà trước trước đó
- Với mỗi nhà
- Nếu không lấy nhà hiện tại, tổng tiền là prev1
- Nếu lấy nhà hiện tại, tổng tiền là prev2 + num
- Chọn giá trị lớn nhất
- Cập nhật prev2 và prev1 cho vòng lặp tiếp theo