45. Jump Game II
Tags:
Medium
Skills:
DP
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài yêu cầu tìm số bước nhảy tối thiểu để đi từ vị trí đầu tiên đến vị trí cuối cùng của mảng
============================
Approach - DP
Phương pháp này sử dụng DP để lưu số bước nhảu tối thiểu cần thiết để đến mỗi vị trí
Ý tưởng chính:
Solution
1function jump(nums: number[]): number {
2 const n = nums.length;
3 const dp = new Array(n).fill(Infinity);
4 dp[0] = 0;
5
6 for(let i = 0; i < n; i++) {
7 for(let j = 1; j <= nums[i] && i + j < n; j++) {
8 dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
9 }
10 }
11
12 return dp[n - 1]
13};=============================
Approach - Greedy
farthest : vị trí xa nhất có thể tới được trong phạm vị các bước nhảy hiện tạicurrent_jump_end : vị trí xa nhất của bước nhảy hiện tại. Khi duyệt đến đúng vị trí này, tăng số bước nhảy lên và cập nhật phạm vi bước nhảy mớijumpsMinh họa thuật toán
jumps = 0, currentJumpEnd = 0, farthest = 0.farthest = max(farthest, i + nums[i]).i === currentJumpEnd), tăng bước nhảy lên, cập nhật phạm vi mới: currentJumpEnd = farthest.jumps.Solution
1function jump(nums: number[]): number {
2 let jump = 0;
3 let farthest = 0
4 let current_end = 0;
5
6 for (let i = 0; i < nums.length - 1; i++) {
7 farthest = Math.max(farthest, i + nums[i]);
8
9 if (i === current_end) {
10 jump++;
11 current_end = farthest;
12 if (current_end >= nums.length - 1) {
13 break;
14 }
15 }
16 }
17
18 return jump;
19};