Jump Game

Bắt đầu từ chỉ số 0, lần lượt thử mọi vị trí có thể tiếp đất, rồi lặp lại thao tác đó từ mỗi vị trí. Nếu bất kỳ nhánh nào đến được chỉ số cuối cùng, đáp án là true. Cách tìm kiếm này chính xác vì nó thử mọi đường đi.

Cách này không ghi nhớ chỉ số nào đã khám phá, nên khi đáp án là false, nó phải loại trừ mọi đường đi. Trong [4, 3, 2, 1, 0, 5], mọi chỉ số trước số 0 đều có thể đến số 0, tạo ra 8 đường đi đến đó. Với 30 chỉ số như vậy, sẽ có hơn 500 triệu đường đi.

Gọi một chỉ số là tốt nếu bạn có thể đi đến cuối từ đó. Chỉ số cuối cùng là tốt, và chỉ số i là tốt nếu có một chỉ số nào đó từ i+1 đến i+nums[i] là tốt. Mỗi chỉ số chỉ phụ thuộc vào các chỉ số ở bên phải nó, vì vậy hãy điền bảng từ phải sang trái và xác định mỗi chỉ số một lần. Trong ví dụ đầu tiên, chỉ số 2 đi đến được chỉ số 5, nên nó là tốt, và chỉ số 0 cũng vậy vì đi đến được chỉ số 2.

Việc xác định một chỉ số vẫn có thể phải quét n ô. Trong [9998, 9997, …, 1, 0, 7], mọi chỉ số đều đi đến được số 0 nhưng không đi xa hơn, nên mỗi chỉ số phải quét toàn bộ phạm vi của nó: khoảng 5 × 10^7 lượt kiểm tra với 10^4 phần tử.

Từ một chỉ số có thể đến được i, bạn có thể đi đến bất kỳ vị trí nào từ i+1 đến i+nums[i], không có khoảng trống. Đoạn đó bắt đầu bên trong khối đã đến được, nên khối mở rộng mà không có khoảng trống và luôn là [0, farthest].

Duyệt i từ trái sang phải. Khi i ≤ farthest, chỉ số i có thể đến được và mở rộng farthest thành max(farthest, i+nums[i]). Nếu i vượt quá farthest, không có chỉ số nào có thể đến được nhảy đến i, và khối không thể vượt qua khoảng trống đó, nên không thể đến được chỉ số cuối cùng. Chỉ giữ lại điểm cuối bên phải là đủ: bạn không quyết định nhảy đến vị trí nào, và mọi vị trí có thể đến ngắn hơn đều nằm bên trong khối.

Trong ví dụ thứ hai, farthest lần lượt là 0, 1, 4 rồi giữ nguyên ở 4 qua ba số 0. Chỉ số 5 nằm ngoài phạm vi đó, nên kết quả là false.