55. Jump Game
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 toán yêu cầu:
Approach - Greedy - Most Optimize
max_reach để lưu vị trí xa nhất có thể nhảy tới tính đến hiện tạimax_reach , nghĩa là không thể tới được vị trí này → return faslemax_reach = max(max_reach, i + nums[i]) (vị trí xa nhất có thể nhảy tới từ các vị trí đã duyệt)trueSolution - Greedy
1function canJump(nums: number[]): boolean {
2 let max_reach = 0;
3 for(let i = 0; i < nums.length; i++) {
4 if(i > max_reach) return false;
5 max_reach = Math.max(max_reach, i + nums[i]);
6 }
7 return true;
8}falsetrueApproach - DP
dp[] với dp[i] là true nếu có thể nhảy đến vị trí i từ vị trí đầu tiên, ngược lại là falsedp= true (vì bạn luôn ở vị trí đầu tiên)i, nếu dp[i] là true, kiểm tra tất cả các vị trí có thể nhảy tới từ i (từ i+1 đến i+nums[i]), gán dp[j]=true.dp[n-1] là true thì trả về true, ngược lại trả về false.Solution - DP
1function canJump(nums: number[]): boolean {
2 const n = nums.length;
3 const dp: boolean[] = Array(n).fill(false)
4 dp[0] = true;
5
6 for(let i = 0; i < n; i++) {
7 if(dp[i]) {
8 for(let j = i + 1; j <= i + nums[i] && j < n; j++) {
9 dp[j] = true
10 }
11 }
12 }
13 return dp[n - 1];
14};