점프 게임 II leetcode 문제
5027 단어 javadynamicprogrammingdp
배열의 각 요소는 해당 위치에서의 최대 점프 길이를 나타냅니다.
귀하의 목표는 최소 점프 횟수로 마지막 인덱스에 도달하는 것입니다.
항상 마지막 색인에 도달할 수 있다고 가정할 수 있습니다.
예 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last 인덱스.솔루션 : Memoization dp 사용(하향식 접근)
class Solution {
public int jump(int[] nums) {
if(nums.length==1)return 0;
int dp[] =new int[nums.length];
Arrays.fill(dp,10001); // since max length is of 10^4 , hence max jump can't exceed 10^4
return solve(nums,0,dp);
}
int solve(int[] nums,int index, int dp[]){
//base cases
if(index==nums.length-1) return 0;
if(index>=nums.length)return 10001;
if(dp[index]!=10001) return dp[index];
//since we are allowed to move i+1,i+2,....i+k give i+k <=i+nums[i]
for(int i = index+1;i<=index+nums[index] ;i++){
dp[index] = Integer.min(dp[index],1+solve(nums,i,dp));
// since every jump that we will make from current index 'index', hence min distance will be distance from current index 'index' to the last index;
}
return dp[index];
}
}
Reference
이 문제에 관하여(점프 게임 II leetcode 문제), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/prashantrmishra/jump-game-ii-leetcode-problem-2p0d텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
