給定一個非負整數陣列
nums，每個元素代表在該位置最多能跳的步數。從索引 0 出發，保證一定能到達最後一個位置。求到達最後一個位置的最少跳躍次數。
Example:
Input: nums = [2,3,1,1,4] Output: 2 (跳到索引 1，再跳到最後)
Intuition
TIP
BFS 思維：每一「跳」相當於一層，在當前層能到達的所有位置中找下一層的最遠邊界。
- 把問題想成 BFS：第 0 層是起點，第 1 層是從起點一跳能到的所有位置…
- 維護當前層的邊界
end和下一層能到的最遠位置farthest - 每次
i到達end時，跳躍次數 +1，更新end = farthest
Approaches
1. DP — O(n^2) / O(n)
- Idea:
dp[i]代表到達位置 i 的最少跳躍次數，對每個位置更新它能跳到的位置。 - Time:
O(n^2)最差情況 - Space:
O(n)
class Solution {
fun jump(nums: IntArray): Int {
val n = nums.size
val dp = IntArray(n) { Int.MAX_VALUE }
dp[0] = 0
for (i in 0 until n) {
for (j in 1..nums[i]) {
if (i + j < n) {
dp[i + j] = minOf(dp[i + j], dp[i] + 1)
}
}
}
return dp[n - 1]
}
}⭐ 2. Greedy (BFS layering) — O(n) / O(1)
- Idea: 維護當前跳躍範圍的邊界，到達邊界時跳躍次數 +1 並擴展到下一範圍。
- Time:
O(n) - Space:
O(1)
class Solution {
fun jump(nums: IntArray): Int {
var jumps = 0
var end = 0
var farthest = 0
for (i in 0 until nums.size - 1) {
farthest = maxOf(farthest, i + nums[i])
if (i == end) {
jumps++
end = farthest
}
}
return jumps
}
}🔑 Takeaways
- Pattern: BFS 分層遍歷 — 用邊界變數模擬 BFS 的層次
- Key trick: 迴圈只到
nums.size - 2（不含最後一個），避免在終點處多算一跳；這種「隱式 BFS」技巧也適用於其他最短路徑問題