Leetcode解题-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.

分析

一道典型的动态规划题，我们用dp[i][j]表示以root为头、triangle[i][j]为结束节点的最短路径长度，则dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]。这个二维递推式可以用一个一维数组来完成，只要每一行都倒着填充就可以了。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        n = len(triangle)
        dp = [float('inf')] * (n + 1)
        min_path = triangle[0][0]
        dp[1] = min_path
        for i in xrange(1, n):
            for j in xrange(i + 1, 0, -1):
                dp[j] = min(dp[j], dp[j - 1]) + triangle[i][j - 1]
        return min(dp)

热评文章