[LeetCode] Jump Game

문제

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

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

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum   jump length is 0, which makes it impossible to reach the last index.

 

Approach

전형적인 DP 문제라고 생각하여 재귀를 쓰는 DP로 구현을 했는데 (메모를 만들고 여기에서 끝에 도달할 수 있는지 없는지 적는 방식)

예상과 달리 메모리 한계 초과로 터져나감

그래서 재귀를 안쓰는 DP로 다시 구현했다. 기존 DP가 앞에서 부터 재귀로 끝에 도달하는 Top-down방식이라면

재귀를 안쓰는 DP는 애초에 끝에서부터 시작하는 Bottom-up 방식.

DP를 썼음에도 불구하고 시간복잡도는 O(n^2)로 상당히 느림

 

Optimization

사실 생각해보면 모든 칸에 대해 이 칸이 끝에 도달할 수 있는지 없는지를 체크할 필요는 없다

길 하나만 찾으면 true이기 때문.

따라서 끝칸에서부터 이 칸이 끝에 도달 할 수 있는지 기록하고 끝에 도달 할 수 있는 칸이 나오면

이 칸이 이전에서 그 끝에 도달 할 수 있는 칸까지 갈 수 있는지를 업데이트 하다가

시작 칸이 가장 마지막으로 찾은 끝에 도달할 수 있는 칸까지 갈 수 있다면 true 고 아니면 false이다

시간복잡도는 O(n)

 

Code

DP: https://github.com/chi3236/algorithm/blob/master/LeetCode_JumpGame_DP.cpp 

chi3236/algorithm

Greedy: https://github.com/chi3236/algorithm/blob/master/LeetCode_JumpGame_greedy.cpp

chi3236/algorithm