2021.06.12 정수삼각형 Solution DFS : 삼각형의 꼭대기에서부터 아래 or 오른쪽아래로 깊이우선탐색을 합니다. DFS로 탐색을 구현할 때 리턴하는 값은 다음과 같이 설정할 수 있습니다. 맨 아래인 경우 : 해당 노드의 값 맨 아래가 아닌 경우 : 해당 노드의 값 = 그 다음노드부터 맨 아래까지의 최대경로 이렇게 설정하면 결국 재귀로 구현한 깊이우선탐색의 최종 반환 값이 원하는 결과가 됩니다. DP : 위의 DFS에서 각 노드를 탐색할 때, 이미 탐색한 적이 있는 경우 메모이제이션 을 활용할 수 있습니다. 해당 노드부터 맨 아래까지의 경로 중 최댓값을 DP 배열에 저장하고, 이미 탐색한 적이 있는 경우 (DP 배열이 초기값이 아닌경우) 에는 메모이제이션 해둔 값을 반환하도록 합니다. Sou..