120. Triangle

120. Triangle

https://leetcode.com/problems/triangle/

문제

풀이(DFS)

DFS 탐색 그래프로 나타내면 다음과 같다.

조건에서 해당 인덱스 또는 해당 인덱스 + 1로 갈 수 있다고 명시하였으므로 dfs(row + 1, col), dfs(row + 1, col + 1)로 하였다.

풀이(결과)

풀이(DP=>bottom up)

bottom에서 시작해서 위로 올라가는 방법으로 하였다. 그래프로 보았을 때 맨 아래에서 할 필요는 없으므로 그 위에 ㅣ-2부터 시작하였고 triangle[i][j]를 갱신하는 방법으로 구현하였다. 예를 들자면
그래프에서 7이 나온 이유는 min(6+4, 6+1) = 7이고 9가 나온 이유는 min(3+7, 3+6) = 9이여서 나온 것이다.

결과(DP=>bottom up)