【LeetCode】三角形最小路径和

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

[

   [],

  [,],

 [,,],

[,,,]

]

自顶向下的最小路径和为 （即， +  +  +  = ）。

【第一种思路】

直接暴力递归，将各种情况进行穷举，但是必定会超时，通过递归的方法我们可以得到核心的递归表达式：
triangle[x][y] += min(triangle[x+1][y], triangle[x+1][y+1]), 这是由于三角形的下一行只比上一行多一个数的规律导致的！

class Solution {

public:

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

       return dfs(, , triangle);

    }

    int dfs(int x, int y,vector<vector<int>>& triangle) {

        if (x == triangle.size() )

            return ;

        return triangle[x][y] + min(dfs(x + , y, triangle),dfs(x + , y + , triangle));

    }

};

【第二种思路】既然有了递归式，就可以把暴力递归改成动态规划了！这里说一个原地动态规划的解法！
类似于搭积木的原理，从底向上，在每一层都取两个数的最小值加到上一层去，一层层累积上去，直到顶部，最短路径就是triangle[0][0]。

class Solution {

public:

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

        for(int i = triangle.size()-; i >= ; --i){

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

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

                // triangle[i+1][j+1]不会越界，第i+1行比第i行多一个值

            }

        }

        return triangle[][];

    }

};

巴特西

【LeetCode】三角形最小路径和

最新文章

热门文章