문제 조건

input

• 2차원 int 배열 triangles

  

• 1 ≤ triangles.len ≤ 500

output

• 거쳐간 경로의 최대 합

문제 해석

• 경로는 현재 위치 기준으로 좌/우 대각선 방향으로 한정
• 시간 복잡도는 여유있음
• DP를 사용하기 적합한 문제
  • 상향/ 하향식 접근 중 상향식 접근이 용이해 보임
  • 하향식 접근을 사용하면 space complexity에서 손해를 볼 수 있음

코드

1. 상향식 접근

   1. DP 배열을 triangles의 마지막 요소로 초기화
   2. 아래에서 2 번째 행부터 역순으로 loop 진행
      1. DP 배열을 인덱스에서 최대 값으로 초기화
      2. 최대 값은 triangles[i][j] + max(dp[j], dp[j+1])
   3. dp[0] 리턴

   def solution(triangle):
       # triangle의 마지막 요소 복사
       dp = triangle[-1][:]
       
       # 아래에서 2 번째 행부터 역순으로 loop
       # i == 행의 요소 개수
       for i in range(len(triangle) - 2, -1, -1):
           
           # i행 아래까지 진행된 dp 배열의 값을 참고
           for j in range(i+1):
               dp[j] = triangle[i][j] + max(dp[j], dp[j+1])
       
       return dp[0]
   

2. 하향식 접근

   1. dp을 triangle.len만큼 복사하니깐, O(N) 공간 복잡도를 가짐
   2. 공간 복잡도가 상수인 상향식 접근 보다 불리

   def solution(triangle):
       h = len(triangle)
       
       dp = [row[:] for row in triangle]
       
       # 두 번째 행부터 시작
       for i in range(1, h):
           for j in range(i+1):
               
               # 좌측 라인
               if j == 0:
                   dp[i][j] += dp[i-1][j]
               
               # 우측 라인
               elif j == i:
                   dp[i][j] += dp[i-1][j-1]
                   
               else:
                   dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])
       
       return max(dp[-1])