dp

Đề 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: