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.

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.

分析：

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

从最底层往上去找，开辟一个二维数组res，其中res[i][j]记录到达该点时，最小的路径和，状态转移方程是res[i][j] = min(res[i+1][j]+triangle[i][j], res[i+1][j+1]+triangle[i][j])，也就是到达这个位置的最小路径和，等于当前的值加上下一层相邻的最小路径和的较小的值，值得注意的是，数组的形式实际是如下的：

[2],

[3,4],

[6,5,7],

[4,1,8,3]

而不是看起来那样的三角形，注意索引就好。

题中说使用 O(n) 的额外空间，一旦理解了这道题的思路，就很容易做了，开辟一个大小为三角形行数大小的数组，每一次状态更新时，在数组中更新就好。

res[j] = min(res[j]+triangle[i][j], res[j+1]+triangle[i][j]);

程序：

//O(n^2) space

class Solution {

public:

    int minimumTotal(vector<vector<int>>& triangle) {

        int m = triangle.size();

        vector<vector<int>> res(m+, vector<int>(m+, ));

        //res[i][j] = min(res[i+1][j]+triangle[i][j], res[i+1][j+1]+triangle[i][j])

        for(int i = m-; i >= ; --i)

            for(int j = ; j < triangle[i].size(); ++j)

                res[i][j] = min(res[i+][j]+triangle[i][j], res[i+][j+]+triangle[i][j]);

        return res[][];

    }

};

//O(n) space

class Solution {

public:

    int minimumTotal(vector<vector<int>>& triangle) {

        int m = triangle.size();

        vector<int> res(m+, );

        //res[j] = min(res[j]+triangle[i][j], res[j+1]+triangle[i][j])

        for(int i = m-; i >= ; --i)

            for(int j = ; j < triangle[i].size(); ++j)

                res[j] = min(res[j]+triangle[i][j], res[j+]+triangle[i][j]);

        return res[];

    }

};

巴特西

LeetCode 120. Triangle三角形最小路径和 (C++)

题目：

分析：

程序：

最新文章

热门文章