Tutorial — Băng qua hẻm núi

Hãy xét các điều kiện để có một bước nhảy hợp lệ giữa hai cột đá $i$ và $j$. Nhận thấy rằng với mỗi cột đá $i$, số lượng cột đá $j > i$ thỏa mãn điều kiện toàn bộ các cột đá ở giữa đều thấp hơn hoặc cao hơn cả hai đầu mút là rất hạn chế.

Nếu coi mỗi bước nhảy hợp lệ là một cạnh có trọng số $1$ trên đồ thị có hướng, bài toán quy về tìm đường đi ngắn nhất từ cột đá $1$ đến cột đá $n$. Với mỗi vị trí $j$, các đỉnh $i < j$ có thể nhảy tới $j$ chính là các vị trí mà $j$ là phần tử lớn hơn đầu tiên bên phải, hoặc $i$ là phần tử lớn hơn gần nhất bên trái, và trường hợp đối xứng với các phần tử nhỏ hơn.

Sử dụng quy hoạch động với $dp[j]$ là số bước nhảy tối thiểu để đến cột đá $j$. Ta có thể duy trì đồng thời hai ngăn xếp đơn điệu gồm một ngăn xếp giảm dần và một ngăn xếp tăng dần khi duyệt $j$ từ $1$ đến $n$, từ đó tìm và cập nhật tất cả các bước nhảy hợp lệ đến $j$ với tổng độ phức tạp thời gian là $O(n)$.