Gọi ~dp_i~ là tồn tại hay không phương án tách ~i~ chữ cái ban đầu thành các từ có trong từ điển của Miku.

Khi đó, ~dp_i = 1~ nếu ~s_{j...i}~ là một từ có trong từ điển của Miku và ~dp_j = 1~.

Rõ ràng, nếu ta kiểm tra việc tồn tại hay không xâu ~s_{j...i}~ tồn tại trong từ điển, độ phức tạp sẽ là ~O~ (~q\times |S| \times n \times 20~), chỉ đủ cho 3 subtasks đầu.

Để tối ưu xuống subtask cuối, ta phải dùng thêm một CTDL để kiểm soát việc kiểm tra trên. Ta có thể sử dụng CTDL Trie hoặc thuật toán Hash để giải quyết vấn đề này. Khi này, độ phức tạp thuật toán sẽ là ~O~ (~q \times |S| \times 20~) hoặc ~O~ (~q \times |S| \times 20 \times log(n)~) tùy vào cách cài đặt.