문제

링크

You are given a 0-indexed array nums of n integers and an integer target.

You are initially positioned at index 0. In one step, you can jump from index i to any index j such that:

0 <= i < j < n
-target <= nums[j] - nums[i] <= target
Return the maximum number of jumps you can make to reach index n - 1.

If there is no way to reach index n - 1, return -1.

이 문제는 DP(동적계획법)으로 풀어야 하는 문제이다.

• 각 위치에서 조건에 맞는 다음 위치로 점프하면서, 해당 위치까지 도달하는 최대 점프 횟수를 저장하면 됨
• 현재 있는 위치는 i로 표현하고 jump할 수 있는 거리는 j로 표현
• arr[n-1]로 갈 수 있는 방법이 없다면 -1 리턴
• nums[j] - nums[i]가 -target 이상 target 이하인 경우

정답 코드

class Solution {
    public int maximumJumps(int[] nums, int target) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int i = 0; i < nums.length; i++) {
            if (dp[i] == -1) continue;

            for (int j = i + 1; j < nums.length; j++) {
                if (Math.abs(nums[i] - nums[j]) <= target)
                    dp[j] = Math.max(dp[j], dp[i] + 1);
            }
        }

        return dp[nums.length-1];
    }
}

풀이

1. dp[]를 nums 배열의 길이만큼 선언한다. dp 배열의 길이가 최대일 경우가 nums.length 만큼 일테니까
2. dp[]를 -1로 채운 후, 시작위치인 dp[0] = 0으로 초기화
3. 현재 위치와 jump할 수 있는 거리 둘다 계산해야하므로 for문 두개 돌려야 함
4. dp[i] == -1이라면 도달 불가능한 위치라는 뜻
5. ⭐️int j = i + 1인 이유: j는 i보다 항상 뒷 번호이어야 하니까
6. ⭐️점프할 수 있는 조건 안에 들어간다면, dp[j]와 dp[i] + 1을 비교하여 더 큰 것 저장
   dp[i] + 1인 이유: 이전까지 누적된 점프 수 + 이번 점프 1번