문제

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

제한사항

• 1 $\leq$ nums.length $\leq$ $10^4$
• 0 $\leq$ nums[i] $\leq$ 1000

접근

Dynamic Programming 방식으로 접근했어요. DP전용 배열을, 시작한다는 의미로 0번째 원소에 count 값으로 0을 초기화해요. 그리고 0번째 원소의 수치만큼 인덱스를 이동시키면 1을 증가시켰어요.

이를 모든 원소를 기준으로 전개해서, i번째 count 값을 과거의 count 값 + 1과 비교해서 최소 값을 초기화해주면 답을 도출해낼 수 있어요.

설명이 부실한거 같으니 진행 흐름을 도식화해서 표현하면 아래와 같아요.

Ary : [2,3,1,1,4]

	2	3	1	1	4
2	0	1	1	10001	10001
3	10001	1(기준!)	1(min(i-1 번째 + 1, 바로 위 원소))	2	2
1	10001	10001	1	2	2
1	10001	10001	10001	2	2
4	10001	10001	10001	10001	2

배열의 최대 길이는 10000이라 안에 원소는 10001을 넘길 수 없어 초기 값을 이렇게 줬어요.

처음에 2차원 배열로 전개했는데, 최대 $10^8$의 int형 공간을 초기화하기 때문에 메모리 초과가 뜨더라구요. 그래서 1차원 배열로 전개를 했어요.

여기서 깨닳은게, 일부 DP 문제는 2차원 배열로 전개해요. 그때 대각선 원소, [i-1][j-1]번째 접근이 없다면 1차원 배열로도 해결할 수 있다는 사실이었어요. 처음에 2차원 배열로 전개해서 1차원 배열로 전개하는데 시간을 많이 낭비했어요...ㅎㅎ. 그래도 이번 경험을 계기로 1차원 전개도 가능하구나~라는 사실을 얻어서 뿌듯하네요.

답안

class Solution {
    public int jump(int[] nums) {
        int[] dp = new int[nums.length];
        for(int i = 0; i < nums.length; ++i){
            dp[i] = (i <= nums[0]) ? 1 : 10001;
        }
        dp[0] = 0;

        for(int i = 1; i < nums.length; ++i){
            int nCnt = nums[i];
            for(int j = i;j <= i + nCnt && j < nums.length; ++j){
                dp[j] = Math.min(dp[i] + 1, dp[j]);
            }
        }
        return dp[nums.length - 1];
    }
}