Sunary' Blog

Đề bài: Các bạn có thể xem tại đây 132-pattern hoặc có thể xem mình diễn giải lại như sau: Dãy số N được gọi là match với 132 pattern nếu như theo thứ tự tồn tại 3 phần tử thuộc N sao cho: N[i] < N[k] < N[j] với điều kiện i < j < k Kiểm tra xem dãy N cho trước có match với 132 pattern không? Ví dụ: input: N = [1, 2, 3, 4] output: False input: N = [3, 1, 4, 2] output: True giải thích: Đơn giản rồi: Với N = [1, 2, 3, 4] thì không khỏa mãn, nhưng với N = [3, 1, 4, 2] thì [1, 4, 2] tương ứng với pattern 132.

Chắc ai từng làm các bài thuật toán cũng từng nghe đến quy hoạch động (DP), thực ra nó không cao siêu khó hiểu như các bạn nghĩ. Lý do mình viết bài này để để tham chiếu, vì các bài trong tương lai mình nghĩ sẽ dùng phương pháp này nhiều. Định nghĩa: Mình tìm kiếm 1 vài chỗ thì thấy DP được định nghĩa khá đầy đủ như sau:

Đề bài: Bài này mình được 1 công ty nào đó hỏi lúc phỏng vấn, dạo gần đây có 1 người bạn gửi cho bài 4sum nên nhớ lại và chọn làm bài đầu tiên cho blog luôn. Cho trước dãy số N, và số k. Đếm tất cả các cặp số hoán vị duy nhất (a, b) sao cho: a + b = k với a, b thuộc N. Ví dụ: input: N = [1, 2, 3, 3, 4] k = 5 output: 2 giải thích: Vì chỉ có 2 cặp số thỏa mãn: (1, 4) và (2, 3) lưu ý: (1, 4) cũng là cặp số (4, 1) nên chỉ đếm 1 lần, tương tự với (3, 2) và (2, 3).