✅ DP

문제

링크

1. 문제 접근 및 해결 로직

대각선 왼쪽 또는 대각선 오른쪽으로만 이동할 수 있으므로 각 경우를 나눠 세어준다.
하지만 입력을 정삼각형 모양이 아니라 직각삼각형 모양으로 받으므로
대각선 왼쪽으로 이동하는 경우는 아래로 한칸 이동하는 것과 같고
대각선 오른쪽으로 이동하는 경우는 아래로 한칸 -> 오른쪽으로 한칸 이동하는 것과 같다.

바로 이전 위치에 따라 현재 위치가 결정되므로 이전 위치가 될 수 있는 두가지 경우 중에 이동 경로에 있는 수의 합이 최대가 되는 경우를 선택한다.

• 정의
  $f(i,j)$ : $i,j$까지 왔을 때, 합이 최대가 되는 경로에 있는 수의 합
• 구하는 답
  $f(n,n)$
• 초기값
  $f(1,1)=num[1][1]$
• 점화식
  $f(i,j)=max(f(i-1,j),f(i-1,j-1))+num[i][j]$

2. 코드

3. 시간 복잡도 분석

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

4. 문제에서 중요한 부분

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