✅ DP

문제

링크

1. 문제 접근 및 해결 로직

가장 먼저 떠오른건 DFS, BFS이다.
하지만 둘 다 완전탐색이므로 경우의 수를 구하면 MxN이다.
각각 500이하의 자연수이므로 문제 없다고 생각하기 쉽지만, 이동할 수 있는 경우가 상하좌우 4가지 이므로 이점도 생각해줘야 한다.
따라서 정확한 경우의 수는 4xMxN 이다. 최악의 경우 4x500x500 를 모두 탐색해야 한다.

경우의 수를 줄이려면 어떻게 해야할까?
특정 지점까지 올 수 있는 경우를 중복해서 또 연산해줄 필요 없으므로 dp-메모이제이션을 사용한다.

• 정리
  $f(i,j)$ : $i,j$까지 올 수 있는 경우의 수
• 구하는 답
  $f(N,M)$
• 초기값
  $f(1,1)=1$
• 점화식
  $(i,j)$에서 $(i_n,j_n)$로 이동
  이미 구했던 곳일 경우 : $f(i,j) += f(i_n,j_n)$
  이미 구하지 않은 곳일 경우 : $f(i,j) += DFS(i_n,j_n)$

2. 코드

3. 시간 복잡도 분석

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

4. 문제에서 중요한 부분

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