【动态规划】【Leetcode】120. Triangle

1.题目描述

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.算法分析

这也是一道考察动态规划的基础题目。首先要搞清楚何为adjacent numbers，在这个题目里面，对于处于(i,j)位置处的数字，上一层中(i-1,j)和(i-1,j-1)是它的adjacent numbers，在下一层中，(i+1,j)和(i+1, j+1)是它的adjacent numbers。我们把从(0,0)走到(i, j)位置处的最短路径和定义为f(i,j)，很显然f(0,0) = triangle[0][0]。要从(0,0)走到(i, j)，那么必须先从(0,0)走到(i-1,j)位置或者(i-1,j-1)位置。因此，f(i, j) = min{f(i-1,j), f(i-1,j-1)} + triangle[i][j]。同时我们应该注意到在边界处的特殊情况，当j == 0时，想走到(i, 0)只能从(i-1,0)走,只有唯一一条路径，因此f(i, 0) = f(i-1, 0) + triangle[i][0]；当j == len(triangle[i])-1时，想走到(i,j)只能从(i-1,j-1)走，也只有一条路径，因此f(i,j)=f(i-1,j-1)+triangle[i][j]。总结一下上述分析就是

3.代码实现

class Solution:
    def minimumTotal(self, triangle):
        """ :type triangle: List[List[int]] :rtype: int """
        rows = len(triangle)
        for i in range(1, rows):
            for j in range(len(triangle[i])):
                if (j == 0):
                    triangle[i][j] = triangle[i - 1][j] + triangle[i][j]
                elif (j == len(triangle[i - 1])):
                    triangle[i][j] = triangle[i - 1][j -1] + triangle[i][j]
                else:
                    triangle[i][j] = min(triangle[i - 1][j], triangle[i - 1][j - 1]) + triangle[i][j]
        ans = min(triangle[-1])
        return ans

代码实现稍微做了一下变形，采用自底向上的计算方法，避免递归调用。

更多动态规划实例，请关注我的公众号