Triangle - Find the minimum path sum from top to bottom

Question

• leetcode120
• lintcode: (109) 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.

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.

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

题解

题中要求最短路径和，每次只能访问下行的相邻元素，将triangle视为二维坐标。此题方法较多，下面分小节详述。

Method 4 - Dynamic Programming

从主章节中对动态规划的简介我们可以知道使用动态规划的难点和核心在于状态的定义及转化方程的建立。那么问题来了，到底如何去找适合这个问题的状态及转化方程呢？

我们仔细分析题中可能的状态和转化关系，发现从triangle中坐标为 $$triangle[x][y]$$ 的元素出发，其路径只可能为 $$triangle[x][y]->triangle[x+1][y]$$ 或者 $$triangle[x][y]->triangle[x+1][y+1]$$. 以点 $$(x,y)$$ 作为参考，那么可能的状态 $$f(x,y)$$ 就可以是：

1. 从 $$(x,y)$$ 出发走到最后一行的最短路径和
2. 从 $$(0,0)$$ 走到 $$(x,y)$$的最短路径和

如果选择1作为状态，则相应的状态转移方程为：

$$f_1(x,y) = min{f_1(x+1, y), f_1(x+1, y+1)} + triangle[x][y]$$

如果选择2作为状态，则相应的状态转移方程为：

$$f_2(x,y) = min{f_2(x-1, y), f_2(x-1, y-1)} + triangle[x][y]$$

两个状态所对应的初始状态分别为 $$f_1(n-1, y), 0 \leq y \leq n-1$$ 和 $$f_2(0,0)$$. 在代码中应注意考虑边界条件。下面分别就这种不同的状态进行动态规划。

• reference
• visualize

class Solution:
    # @param triangle, a list of lists of integers
    # @return an integer
    def minimumTotal(self, triangle):
        if len(triangle) == 0: return 0
        array = [0 for i in range(len(triangle))]
        array[0] = triangle[0][0]
        for i in range(1, len(triangle)):
            for j in range(len(triangle[i]) - 1, -1, -1):
                if j == len(triangle[i]) - 1:
                    array[j] = array[j-1] + triangle[i][j]
                elif j == 0:
                    array[j] = array[j] + triangle[i][j]
                else:
                    array[j] = min(array[j-1], array[j]) + triangle[i][j]
        return min(array)

sol=Solution()
triangle=[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
sol.minimumTotal(triangle)