# @param {Integer[]} nums # @return {Integer} def jump(nums) last=0 n=nums.size dp=[0]*n (0...n).each do|i| dp.fill(dp[i]+1,last+1..[n-1,i+nums[i]].min) last=[last,[n-1,i+nums[i]].min].max end dp[-1] end

간단한 문제지만 이 풀이 방식이 그다지 간단하지는 않기 때문에 설명해 보겠습니다. 일단 기본적으로 현재 칸까지 횟수가 k고, 이 칸에서 p칸을 갈 수 있다고 합시다. 그런데 앞에 횟수가 k인 경로가 확정된 칸이 몇 칸 더 있다면 그 칸으로 가는 건 손해입니다. 따라서 값이 확정된 칸들 바로 뒤부터 갈 수 있는 가장 먼 위치까지 DP 배열을 갱신합니다. 또한, (1인 구간에서 우측으로 확장) -> (2인 구간에서 우측으로 확장) -> (3인 구간에서 우측으로 확장)과 같은 방식으로 진행되기 때문에, 어떤 위치에서 확정된 마지막 칸까지는 최대 1만큼 차이가 납니다. 그래서 이러한 방식으로 DP를 갱신해 줘도 결과는 동일하게 나오게 되며, 이때 시간복잡도는 O(n)입니다.