목록triangle (1)

Scribbling

LeetCode: 120. Triangle

전형적인 DP 문제 class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: dp = [[0] * (i+1) for i in range(len(triangle))] dp[0][0] = triangle[0][0] for i in range(1, len(triangle)): dp[i][0] = dp[i-1][0] + triangle[i][0] for j in range(1, i): dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] dp[i][-1] = dp[i-1][-1] + triangle[i][-1] return min(dp[len(triangle)-1])
Computer Science/Coding Test 2021. 11. 3. 20:13
이전 Prev 1 Next 다음