Pattern · Tham lamTrung bình
Trò Chơi NhảyJump Game
Hiểu bài
Cho mảng nums, nums[i] là số bước tối đa có thể nhảy từ ô i.
Bắt đầu ở ô 0, trả về true nếu nhảy được tới ô cuối cùng.
ts
nums = [2,3,1,1,4] → true // 0→1→4 hoặc 0→2→3→4
nums = [3,2,1,0,4] → false // kẹt ở ô có giá trị 0, không vượt qua đượcÝ chính kiểu tham lam (Greedy): quét từ phải sang trái, giữ "đích gần nhất chạm được".
- Nếu từ ô i nhảy tới được đích đó, thì i trở thành đích mới.
- Cuối cùng kiểm tra đích đã lùi về ô 0 chưa.
Cách cơ bản
O(n²) time, O(n) spacets
function canJumpDP(nums: number[]): boolean {
const n = nums.length
const reachable = new Array(n).fill(false)
reachable[n - 1] = true
for (let i = n - 2; i >= 0; i--) {
// thử mọi bước nhảy từ ô i
for (let step = 1; step <= nums[i]; step++) {
if (reachable[i + step]) { reachable[i] = true; break }
}
}
return reachable[0]
}Vì sao cách này chậm:
Cách này thử mọi bước nhảy tại mỗi ô và lưu bảng "có tới được không" → O(n²).
Chỉ cần theo dõi một biến đích gần nhất là đủ, giảm về O(n) time, O(1) space.
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.