120. Triangle

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

Triangle - LeetCode

 

dp문제

 

삼각형 밑에까지 가면서 가장 최소가 되는 길의 값을 리턴하는 문제

 

triangle과 같은 구조의 dp 배열을 생성하고 

 

현재시점에서 경로값을 누적해서 최소값을 dp값으로 주면 풀수 있음.

 

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        
        dp = [ [ 0 for m in range(len(triangle[j]))] for j in range(len(triangle))]
        
        dp[0][0] = triangle[0][0]
        
        
        
        for r in range(1, len(triangle),1):
            
            for c in range(len(triangle[r])):
                
                if c == 0:
                    dp[r][c] = dp[r-1][c] + triangle[r][c]
                elif c == len(triangle[r])-1:
                    dp[r][c] = dp[r-1][c-1] + triangle[r][c]
                else:
                    dp[r][c] = min(triangle[r][c]+dp[r-1][c-1], triangle[r][c]+dp[r-1][c])
        
        return min(dp[-1])