[알고스팟] JUMPGAME - 외발 뛰기 (C++)

문제

https://algospot.com/judge/problem/read/JUMPGAME

algospot.com :: JUMPGAME

 

풀이

간단한 다이나믹 프로그래밍 문제

 

해당 위치에서 끝에 도달이 가능한지의 여부를 is_pos_board에 저장해두어 중복된 호출을 방지하여 최적화한다.

해당 위치의 도달 여부가 기록되어있다면 바로 그 값을 반환하고 아니라면

왼쪽과 오른쪽으로 이동하는 경우를 재귀호출하여 반환된 값을 기록한다.

 

코드