[이코테] 다이나믹 프로그래밍_정수 삼각형 (python)

문제

: 맨 위층부터 아래로 내려가면서 수를 더함. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택 가능.
맨 아래줄에 도달했을 때, 합이 최대가 되는 경로에 있는 수의 합은?

• 테스트 케이스
  5
  7
  3 8
  8 1 0
  2 7 4 4
  4 5 2 6 5

• 답
  30

나의 풀이

1. 탑다운(재귀 함수)

def plus(n, x, y, arr):
	
	# 맨 꼭대기 지점
	d[0][0] = arr[0][0]
	# 이미 계산된 값인 경우, 그 값을 리턴
	if d[x][y] != 0:
		return d[x][y]
	
	# 대각선 왼쪽 or 오른쪽에서 내려오는 경우
	# list 범위를 벗어날 경우 -1
	left = plus(n - 1, x - 1, y - 1, arr) if x > 0 and y > 0 else -1
	right = plus(n - 1, x - 1, y, arr) if x > 0 and y < n - 1 else -1
	
	# 대각선 왼쪽 or 오른쪽 중에서 더 합이 큰 경우 + 현재 지점의 수
	d[x][y] = max(left, right) + arr[x][y]
	return d[x][y]
    
n = int(input())
triangle = [list(map(int, input().split())) for _ in range(n)]

# 각 지점마다 합이 최대가 되는 경우를 담을 list
d = [[0] * i for i in range(1, n + 1)]
# 경로의 끝, 즉 마지막 행의 각 열마다 합계 계산

for i in range(n):
	plus(n, n - 1, i, triangle)
    
# 삼각형의 가장 아래까지 도달 했을 때 가장 합이 큰 경우는?
print(max(d[-1]))

2. dp 테이블에 담아가며

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]

dp = []    

for x in range(1, n): # 두번째 행부터 확인
    for y in range(x + 1): # x열까지 확인
        # 왼쪽 위에서 내려올 때
        up_l = 0 if y == 0 else dp[x - 1][y - 1]
        # 바로 위에서 내려올 때
        up = 0 if y == x else dp[x - 1][y]
        dp[x][y] = max(up_l, up) + dp[x][y]
            
print(max(dp[n - 1]))       

• 이미 계산된 값인 경우 dp 테이블에 담겨있으므로, 그걸 꺼내서 계산