[Leetcode]120. Triangle(C++)

题目描述

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.

解题思路

从题目中可以知道，对第 i 排的第 j 个位置，可以到达的路径只有 (i - 1, j - 1) 和 (i - 1, j) 因此不难想到用动态规划的思路，假设 min_sum[i][j] 表示到达 (i,j) 最小的路径和，则有：

min_sum[i][j] = triangle[i][j] + min(min_sum[i - 1][j - 1], min_sum[i - 1][j])

根据这个状态转移方程进行计算即可，并且可以发现在计算每一层时只需要当前层和上一层的结果，因此只需要两个 std::vector 分别保存即可，代码如下：

#include <vector>

class Solution {
public:
    int minimumTotal(std::vector<std::vector<int>>& triangle) {
        int n = triangle.size();
        std::vector<int> min_sum{triangle[0][0]};
        int current_min_sum = min_sum.front();
        for (int i = 1; i < n; i++) {
            std::vector<int> next_level(i + 1, 0);

            // for the first and last element in each level, there is only 1
            // possible path
            next_level.front() = triangle[i].front() + min_sum.front();
            next_level.back() = triangle[i].back() + min_sum.back();

            current_min_sum = std::min(next_level.front(), next_level.back());
            for (int j = 1; j < i; j++) {
                next_level[j] =
                    triangle[i][j] + std::min(min_sum[j - 1], min_sum[j]);
                current_min_sum = std::min(current_min_sum, next_level[j]);
            }
            min_sum = next_level;
        }

        return current_min_sum;
    }
};

时间复杂度: O(n^2)
空间复杂度: O(n)

GitHub 代码同步地址： 120.Triangle.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions