MENU

LeetCode120. Triangle(动态规划)

2019 年 03 月 23 日 • 阅读: 1024 • LeetCode阅读设置

LeetCode120. Triangle(动态规划)

  • Medium
  • Accepted:172,497
  • Submissions:447,076

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.


链接

https://leetcode.com/problems/triangle

题意

给定一个三角形,找出从顶到底的最小路径和,每一步只能移到下一行相邻(左下右下)的两个数字。

题解

对于一个数字,有往左下和右下两种走法。这样的话考虑一共n行,那么时间复杂度就是$O(2^n)$。

实际上这样做的话会产生很多重复计算,对于样例,第二层的3和4都可以选择5,所以5往下的就会被重复计算。

一个可行的办法是“记忆化搜索”,或者我们直接采用自底向上的动态规划。

从第n-1层开始,对该层进行循环然后计算该层的某个数加上第n层的某个数,即左下和右下取一个最小值,然后一层一层往上走,到达第一层后得到的就是结果。

假设$dp[i][j]$表示第i层第j个数到最底层路径的最小值,那么动态规划方程为:$dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + dp[i][j]$。

[
     [2],          [11]
    [3,4],   -->  [9,10]
   [6,5,7],      [7,6,10]
  [4,1,8,3]   
]

平均时间复杂度$O(n^2)$,如果直接在原数组上操作的话,空间复杂度$O(1)$。

代码

  • Runtime: 8 ms, faster than 99.87% of C++ online submissions for Triangle.
  • Memory Usage: 9.9 MB, less than 94.41% of C++ online submissions for Triangle.
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        for (int i = n - 2; i >= 0; --i)
        {
            int m = triangle[i].size();
            for (int j = 0; j < m; ++j)
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
        }
        return triangle[0][0];
    }
};

The end.
2019年3月23日 星期六