【动态规划】三角形最小路径和

链接 https://leetcode-cn.com/problems/triangle/

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

定义：$dp[i][j]$表示从索引号$(0,0)$到索引号$(i,j)$的最小路径和

边界：$dp[0][0]=triangle[0][0]$​​​

状态转移方程：$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}$​​

说明：当前的最小值，等于上一行左右两列的最小加上当前值

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        '''动态规划'''
        ''' 自顶向下： 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]
        
        '''自顶向下'''
        for i in range(1,lens):     #假设有5层，那么i是1到4
            for j in range(i+1):    #j是0到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