Tutorial — Tháp Tinh Thể

Hãy xét sự thay đổi vị trí của các viên tinh thể trên lưới tọa độ khi di chuyển qua từng bước. Mối liên hệ giữa chỉ số của viên tinh thể và vị trí của nó phụ thuộc vào tính chẵn lẻ của chỉ số đó.

Hai viên tinh thể được đặt xếp chồng lên nhau trong cùng một tháp bắt buộc phải có chỉ số mang tính chẵn lẻ khác nhau. Do đó, việc tạo một tháp loại $r$ tương đương với việc chọn một dãy con các viên tinh thể loại $r$ có chỉ số đan xen chẵn lẻ.

Duyệt qua dãy từ đầu đến cuối và sử dụng chiến thuật tham lam kết hợp quy hoạch động. Với mỗi loại $r$, duy trì chiều cao hiện tại và tính chẵn lẻ của chỉ số viên tinh thể gần nhất được chọn để cập nhật kết quả trong thời gian $O(n)$.