Xin nốt cái example luôn. Đọc sơ qua thì hướng giải quyết có thể là greedy algorithm.Mình có 1 cái problem như hình, có runtime constraint nên không thể brute force được, các ae vào giúp đỡ. Mình cám ơn
Các ae lưu ý là 2 là winter chứ k phải summer
Mình không nghĩ là dùng pure greedy được do nó có cái subset số 3 ( cái cả 2 ss) thì không biết dùng greedy như nào
Chính xác là phải dùng dynamic programming để giải
Là sao thím ơi, mình cũng không hiểu cho lắm
Bài này có thể giải theo 2 cách, dùng recursion hoặc dynamic programming. Cơ bản là mình phải tìm ra tất cả giá trị p (có thể có rất nhiều p) có thể xảy ra với a và b cho trước. Sau cùng là tìm ra giá trị p lớn nhất.
Dùng recursion như nào vậy thím ơi, thử hết value trong cái subset thứ 3 ( cả 2 season) à ?
Đúng rồi, với mỗi item cứ thử cả 3 trường hợp:
maxPoint(i, cw, cs) { // Xét item thứ i, với số tiền còn lại cho mùa đông (cw) và mùa hạ (cs)
if (i >= n) return 0;
p = maxPoint(i + 1, cw, cs) // không mua item
if (s[i] & 1 && c[i] <= cs) { // mua mùa hạ
p = max(p, p[i] + maxPoint(i + 1, cw, cs - c[i]))
}
if (s[i] & 2 && c[i] <= cw) { // mua mùa đông
p = max(p, p[i] + maxPoint(i + 1, cw - c[i], cs))
}
return p
}Cám ơn bạn, nhân tiện cho mình hỏi, bài này độ khó chắc tầm medium trên leetcode nhỉ ?
Hard for sure luôn bạn
Cám ơn bạn nhiều
Bạn luyện kiểu gì mà giỏi thế nhỉ, mình easy còn chưa làm đc
Chăm chỉ + có lộ trình rõ ràng là được thôi bạn.
Bác chia sẻ rõ được k ạ, kiểu trước bác có follow lộ trình nào ko?
Lộ trình sơ sơ thì trước minh cũng share trong thớt này vài lần rồi, thím có thể search lại.
Mấy bài kiểu này nếu bạn không phải một coder có kinh nghiệm đang muốn thử thách bản thân thì nên bỏ qua. DP hại não vl
2 kỹ thuật có thể dùng chung cho 1 mục đích nhưng phương thức hoạt động khác nhau. Thông thường, DP là phiên bản cải tiến của recursion.recursion thì cũng là DP thôi chứ
Bác cho em hỏi em dùng C# để luyện algo, mà xử lý array trong C# kiểu thêm phần tử các thứ k dễ như JS thì em có đc convert sang List để cho tiện Add Remove khi phỏng vấn k nhỉ
Được thôi bạn, mấy cái này không quan trọng lắm đâu
