📖 동적계획법(Dynamic Programming) > 정수 삼각형
📖What I thought
그냥 딱 dp문제라고 생각했는데 너무 오랜만에 dp 문제를 풀어서 코드로 구현하는데까지 시간이 조금 걸렸당.. ㅎㅎ
📖풀이
📎다이나믹 프로그래밍(Bottom-Up)
def solution(triangle):
n = len(triangle)
dp = [[0 for _ in range(i+1)] for i in range(n)]
dp[0][0] = triangle[0][0]
for i in range(1, n):
for j in range(0, i+1):
if j == 0:
dp[i][j] = dp[i-1][j] + triangle[i][j]
elif j == i:
dp[i][j] = dp[i-1][j-1] + triangle[i][j]
else:
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
# print(dp)
return max(dp[-1])📖What I learned
- 완전 기본적인 dp 문제!