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日星期六