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]; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter