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的方向想。 dp的四要素

• state
• function
• init state
• result

这里dp[i][j]代表的是以triangle[i][j]为终点的路径的最小值，因为dp[i][j]的上面一层最多只有两种选择， （在左边界和右边界时只有一种选择），所以就可以推出function是

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

follow up

因为只有两层之间有联系，所以可以只用两个n为长度的array就可以

Solution

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if not triangle:
            return 0
        rowNum = len(triangle)
        dp = [[sys.maxint for i in range(rowNum)]for j in range(rowNum)]
        dp[0][0] = triangle[0][0]
        for i in range(1, rowNum):
            for j in range(i+1):
                if j == 0:
                    dp[i][0] = dp[i-1][0] + triangle[i][0]
                elif j == i:
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j]
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

        minResult = sys.maxint
        for i in range(rowNum):
            if dp[rowNum-1][i] < minResult:
                minResult = dp[rowNum-1][i]

        return minResult

空间优化

注意，不能直接dp1=dp2，因为这样它们指向的是同一个地址，那么dp2在变化的时候dp1指向的array也会 随着变化，就会导致结果不对，需要新建一个array，用dp1 = list(dp2)

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if not triangle:
            return 0
        rowNum = len(triangle)
        if rowNum == 1:
            return triangle[0][0]
        dp1 = [sys.maxint for i in range(rowNum)]
        dp2 = [sys.maxint for i in range(rowNum)]
        dp1[0] = triangle[0][0]
        for i in range(1, rowNum):
            for j in range(i+1):
                if j == 0:
                    dp2[0] = dp1[0] + triangle[i][0]
                elif j == i:
                    dp2[j] = dp1[j-1] + triangle[i][j]
                else:
                    dp2[j] = min(dp1[j-1], dp1[j]) + triangle[i][j]
            dp1 = list(dp2)

        return min(dp2)

Reference