✅ DP

문제

링크

1. 문제 접근 및 해결 로직

1. 오른쪽이나 아래쪽으로만 이동할 수 있다.
   -> 오른쪽으로 간 경우, 아래쪽으로 간 경우로 나누어 다음칸을 결정
2. 이전칸의 점프 횟수가 몇이었는지에 따라 현재칸 기준으로 이전칸이 뭐였는지 알 수 있다.
   -> 점프 횟수를 저장하며 점프 횟수에 따라 다음칸을 결정

• 정의
  $f(i,j)$ : $i,j$까지 이동할 수 있는 경로의 개수
• 구하는 답
  $f(N,N)$
• 초기값
  $f(1,1)=1$
• 점화식
  오른쪽으로 이동 : $f(i,j+jump)+=f(i,j)$
  아래쪽으로 이동 : $f(i+jump,j)+=f(i,j)$
  $jump=map[i][j]$

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항