10-16 LeetCode 120. Triangle

Triangle

Description

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).

给你一个三角形，找出从顶部到底部路径最小的路径值，每一步都只能找下一层与当前数相邻的两个数。

例子

如上述那个三角形，最短路径值为11. 2 + 3 + 5 + 1 = 11

Solution 1:

这个题目是一个很典型的动态规划的问题。动态规划适合解决的问题有如下特征：

1. 可以转化为求解规模更小一些的的相同的子问题

2. 子问题有最优解

3. 多阶段规划

拿这个题目来说，想求到第一层的最短路径，可以先求出到第二层的每个点的最短路径，然后加上顶层的2就是最短路径。想求到第二层每个点的最短路径，可以先求出到第三层每个点的的最短路径，然后分别与第二层对应点相加求出第二层每个点的最短路径，这样依次类推下去。

代码

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        height = len(triangle)
        result = triangle[-1]
        for i in range(height-1, 0, -1):
            temp = result[:]
            result = []
            for j in range(i):
                result.append(min(triangle[i-1][j]+temp[j], triangle[i-1][j]+temp[j+1]))
        return result[0]

感想

想做这个项目的时候没想到这学期课这么多，这几天学业压力比较重，有很多的实验，作业需要完成。我刷题都是在LeetCode上点击Pick problem随机选的，很幸运又找到个简单的题，让今天的任务可以很快完成。由于比较忙，自己做完这题就没去看别人的分析，不知道有没有什么更好的方法，可以自己去搜索。