No Limitation
[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
'프로그래밍' 카테고리의 다른 글
[DP] N으로 표현 - 프로그래머스 (0) | 2022.02.02 |
---|---|
[DP] 동전 1 - 백준 (0) | 2022.02.02 |
[구현,시뮬레이션] 빗물 - 백준 (0) | 2022.01.31 |
[Greedy, Activation Selection Problem] 단속 카메라 - 프로그래머스 (0) | 2022.01.31 |
[Greedy, MST] 섬 연결하기 - 프로그래머스 (0) | 2022.01.31 |