Daily Leetcode 120. Triangle

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

问题描述：

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

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

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

题目分析：

这一题乍一看，不注意约束条件，会觉得是一条easy难度的题目，就觉得是在等腰三角形中从上至下找一条最短和路径，然而题目中加上了约束条件：只能往下或者往右下移动。我们可以利用动态规划解决这种存在约束条件的路径求解问题。

从(i,j)位置向下走得到的最短路径长度：

mp(i,j)=min{mp(i+1,j), mp(i+1,j+1)}+triangle(i,j)

我们可以从等腰三角形的底层向上一步步推，这样到最顶层就能够得到最短和路径，以原题所给示例为例子：

mp(3,0) = 4
mp(3,1) = 1
mp(3,2) = 8
mp(3,3) = 3

mp(2,0) = min{mp(3,0), mp(3,1)} + triangle(2,0) = 7
mp(2,1) = min{mp(3,1), mp(3,2)} + triangle(2,1) = 6
mp(2,2) = min{mp(3,2), mp(3,3)} + triangle(2,2) = 10

mp(1,0) = min{mp(2,0), mp(2,1)} + triangle(1,0) = 9
mp(1,1) = min{mp(2,1), mp(2,2)} + triangle(1,1) = 10

mp(0,0) = min{mp(1,0), mp(1,1)} + triangle(0,0) = 11

由上述推导，我们可以得出在这个例子中，最短和路径应该是2+3+5+1 = 11

代码：

def minimumTotal(self, triangle):
    """
    :type triangle: List[List[int]]
    :rtype: int
    """
    length = len(triangle)
    if length == 0: return 0
    if length == 1: return triangle[0][0]
    
    mp = [[0]*length for i in range(length)]
    mp[length - 1] = triangle[length - 1]
        
    for i in range(length - 2, -1 , -1):
        for j in range(len(triangle[i])):
            mp[i][j] = min(mp[i + 1][j], mp[i + 1][j + 1]) + triangle[i][j]

    return mp[0][0]