[dynamic programming] triangle minimum path sum

link https://leetcode-cn.com/problems/triangle/

Given a triangle triangle , Find the smallest sum from the top down .

Each step can only move to adjacent nodes in the next row . Adjacent nodes What I mean here is Subscript And The upper node subscript Equal to or equal to The upper node subscript + 1 Two nodes of . in other words , If it is in the subscript of the current line i , So the next step is to move to the subscript of the next line i or i + 1 .

Definition ：$dp[i][j]$ Indicates a slave index number $(0,0)$ To index number $(i,j)$ The minimum path of and

The border ：$dp[0][0]=triangle[0][0]$​​​

State transition equation ：$dp[i][j]=\{\begin{array}{ll}min(dp[i-1][j],dp[i-1][j-1]),& j\ne 0ori\\ dp[i-1][0]+triangle[i][j],& j=0\\ dp[i-1][i-1]+triangle[i][j],& j=i\end{array}$​​

explain ： The current minimum , Equal to the minimum of the left and right columns of the previous row plus the current value

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        ''' Dynamic programming '''
        '''  The top-down ： dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j] j != 0 or i dp[i][j] = dp[i-1][0] + triangle[i][j] j == 0 dp[i][j] = dp[i-1][i-1] + triangle[i][j] j == i '''

        lens = len(triangle)
        dp = [[0]*lens for _ in range(lens)]
        dp[0][0] = triangle[0][0]
        
        ''' The top-down '''
        for i in range(1,lens):     # Suppose there is 5 layer , that i yes 1 To 4
            for j in range(i+1):    #j yes 0 To i
                if j == 0:
                    dp[i][j] = dp[i-1][0] + triangle[i][j]
                elif j == i:
                    dp[i][j] = dp[i-1][i-1] + triangle[i][j]
                else:
                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]
        ans = dp[lens-1][0]
        for num in dp[lens-1]:
            ans = min(ans,num)

        return ans