Violet_7
Senior Member
8/7/2022:
nếu houses[i.] == 0 -> nhà này có thể có nhiều màu, add lần lượt các màu và cost của có vào dp
nếu houses[i,] != 0 -> chỉ add màu nhà đó và cost lúc đó bằng 0
- 1 Câu hard khó, nhưng khó ở chỗ code khá dài vì nhiều dữ liệu
- Nhìn vào đề bài: yêu cầu min cost cho target group, 1 group là gồm các nhà có màu liên tiếp
- như vậy phải tối ưu
- nhận thấy 1 key khá quan trọng, số group sẽ tăng nếu houses[i.] != houses[i - 1]
- tạo mảng 2 chiều dp, trong đó dp[i.][j.] là min cost có i group và kết thúc tại màu j
- tạo hàm add để xét màu nhà thứ i vào cái dp
nếu houses[i.] == 0 -> nhà này có thể có nhiều màu, add lần lượt các màu và cost của có vào dp
nếu houses[i,] != 0 -> chỉ add màu nhà đó và cost lúc đó bằng 0
- Về hàm add thì nhìn vào code , làm câu này 1 tiếng nên h mệt, lúc nào khỏe thì viết tiếp
- Nói chung là câu này ý tưởng cx khá dễ đoán mất 10p để nghĩ ra, không quá khó để nghĩ ra mà lúc code loạn vl vì nhiều dữ kiện quá dẫn đến code mất 50 phút
- Code : https://leetcode.com/submissions/detail/741509252/ (đã cố gắng viết gọn nhất có thể)
Last edited: