Q2 Jump Game II - LeetCode 45
Wed Mar 01 2023 14:04:43 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
//this is a dp problem , count stairs with minimum jumps
public int jump(int[] nums) {
int n = nums.length ;
//every index stores minimum number of jumps from itself to last index
//we take Integer to store null for indexes from where there is no path
Integer dp[] = new Integer[n];
//jump from n to n will be 0
dp[n-1] = 0;
/*
while iterating from right to left find minimum jumps of from that index
to the last index
*/
for(int i = n - 2;i >=0 ;i--){
//if jumps are greater than 0
if(nums[i] > 0){
int min = Integer.MAX_VALUE;
/*
take jumps from 1 to nums[i] from current index amd see which
next index gives you the minimum ans
*/
for(int j = 1 ; j <= nums[i] && i+j < n ;j++){
//take minimum jumped index answer
if(dp[i+j] != null)
min = Math.min(min , dp[i+j]);
}
//now add 1 for your cell's jump
// if all jumps lead to null, min will stay as it is
if(min!= Integer.MAX_VALUE){
dp[i] = min+1;
System.out.print(dp[i]);
}
}
}
return (int)dp[0];
}
}
content_copyCOPY
https://leetcode.com/problems/jump-game-ii/
Comments