Daily LeetCode 120. Triangle

前几天Mac的键盘再次连击了，今天刚修好，接着来刷算法题。

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

Medium

问题描述：

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.

思路及代码：

给定一个“金字塔”数组，我们需要找到一条从第一层到最后一层的路径，保证这条路径的权值和是最小的，同时，题目还限定了向下走的方式，每次只能往相邻节点走。

我们可以先从自己解决问题的角度出发，思考解决方法。就拿题目中的例子来说，第一层，选择2；第二层，选择2附近的两个数（3，4）中较小的那个（3）；再从3出发，接着向下选择直到最后一层，最终得到一条权值最小的路径（2->3->5->1）。

为了方便代码的编写，我们选择从底向上的方式：

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if len(triangle) == 1:
            return triangle[0][0]

        for i in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[i])):
                triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])

        return triangle[0][0]