[DP] 정수 삼각형 - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 

코딩테스트 연습 - 정수 삼각형

 

Fact Finding

---

• Index를 이용해 해당 노드 별 max값을 저장한 memo 이용
• Recursion을 이용하여 노드 탐색

 

def depth_search(triangle, start, i, j, memo = {}, sums1=0, sums2=0) :
    if (i, j) in memo :
        return memo[(i, j)]
    if i == len(triangle):
        return max(sums1, sums2)
    sums1 = depth_search(triangle, start, i+1, j, memo) + triangle[i][j]
    sums2 = depth_search(triangle, start, i+1, j+1, memo) + triangle[i][j]
    memo[(i, j)] = max(sums1, sums2)
    return memo[(i, j)]

def solution(triangle):
    start = triangle[0][0]
    answer = 0
    answer = depth_search(triangle, start, 0, 0)
    return answer