Leetcode 120.Triangle

这道题的大概意思是，给一个数字构成的三角形，要求找出一条路径使得路径数字之和最小。

比如下面这个三角形的数字和最小的路径就是2+3+5+1=11

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

类型：动态规划

用T表示三角形对应的二维数组，dp表示当前行各个位置上的路径最小和，采用从底向上的计算方式，可以得到递推公式为dp[j] = T[i][j] + min(dp[j], dp[j + 1])，其中i代表行，j代表列。

算法实现

def minimumTotal(self, triangle):
    dp = triangle[-1]
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(i + 1):
            dp[j] = triangle[i][j] +  min(dp[j], dp[j + 1])
    return dp[0]

还算简单。