Kiến thức cần có: Giá trị kì vọng, tìm đường đi ngắn nhất.

Trước mắt ta cần phải tính xác xuất ta sẽ chọn đi ~x~ bước không phụ thuộc vào số nút xúc xắc tung được. Đặt ~X~ là sự kiện tung xúc xắc và ~Y~ là sự kiện chọn số bước để di chuyển, theo đề bài ta có thể tính được:

$$ P(Y = y) = \sum_{x} P(X = x, Y = y) = \sum_{x} P(X = x) \cdot P(Y = y | X = x) = \sum_{x} P_x \cdot G(x, y). $$

Theo đề bài ta có thể hiểu yêu cầu là tìm một đường đi sao cho khi ta chọn đi trên đó, số bước ta kì vọng phải đi là ít nhất có thể. Bây giờ, gọi ~u_1, u_2, \dots, u_n~ là một đường đi ~P~ bất kì với ~u_1 = 1~ và ~u_n = N~ và ~E_P~ là hàm tính số bước kì vọng của ~P~, hiển nhiên đặt ~E_P[u_x] = 0~ với trường hợp ~x \ge n~, sau đó theo đề bài ta có: $$ E_P[u_i] = P(Y = 1) \cdot E_P[u_{i + 1}] + \dots + P(Y = K) \cdot E_P[u_{i + K}] + 1 \forall 1 \le i < n. $$ Như vậy, đề bài yêu cầu tìm đường đi ~P~ sao cho ~E_P[1]~ là nhỏ nhất có thể.

Đặc biệt, ~E_P~ có một tính chất thú vị đó là: ~E_P[u_i] \ge E_P[u_{i + 1}]~. Hàm này cơ bản là dựa trên hàm khoảng cách nên mang tính chất tương tự. Do đó ta có thể thấy, đường đi ~P~ càng ngắn thì giá trị ~E_P[1]~ cũng tối ưu theo. Cho nên ta có thể dùng BFS tìm đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~N~ rồi sau đó tính hàm ~E_P~ với đường đi này sau. Ta cũng có thể tối ưu việc tính hàm ~E_P~ bằng kĩ thuật nhân ma trận nhưng với giới hạn bài này thì không cần thiết.

Độ phức tap: ~\mathcal{O}(NK)~ (nếu không nhân ma trận), ~\mathcal{O}(N + K^3 \cdot \log(N))~.

Với bài này ta cũng có một lời giải thú vị khác nữa là ta có thể thay thế hàm ~E_P~ cho hàm khoảng cách trong BFS và như vậy ta có thuật kết hợp BFS + nhân ma trận.