算法设计与分析-Week9

发表于 | 更新于

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.

解题思路

本题要在一个三角形中从上到下找到最短路径和。
要找到这样一条路径，使用贪心算法是不行的，必须遍历三角形的每个位置。我们可以发现，到达第i行第j列的元素的最短路径是到达第i-1行的第j-1列和j列的较小值再加上第i行第j列的值。因此可以利用动态规划，自顶向下推导，先求出上面的最短路径和，逐步求到最后一行。另外，我们可以发现，我们每次推导某一行的最短路径和的时候，只需要上一层的最短路径和，再往上就不需要了，因此我们为了节省空间，可以只申请一个长度为n的数组，n为三角形的行数，并从行末往前遍历，这样的算法空间复杂度为\(O(n)\)，时间复杂度为\(O(n^2)\)。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        if(n == 0) return 0;
        vector<int> dist(n, 0);
        dist[0] = triangle[0][0];
        for(int i = 1; i < n; i++) {
            dist[i] = triangle[i][i] + dist[i-1];
            for(int j = i - 1; j > 0; j--) {
                if(dist[j-1] < dist[j])
                    dist[j] = dist[j-1] + triangle[i][j];
                else 
                    dist[j] = dist[j] + triangle[i][j];
            }
            dist[0] = triangle[i][0] + dist[0];
        }
        int min = dist[0];
        for(int i = 1; i < n; i++) {
            if(dist[i] < min)
                min = dist[i];
        }
        return min;
    }
};
0%