Leetcode120.Triangle三角形最小路径和

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

例如，给定三角形：

[

[2],

[3,4],

[6,5,7],

[4,1,8,3] ]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

至上到下的动态规划



class Solution {

public:

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

        int len = triangle.size();

        vector<int> dp(len, 0);

        dp[0] = triangle[0][0];

        for(int i = 1; i < len; i++)

        {

            for(int j = i; j >= 0; j--)

            {

                if(j == i)

                {

                    dp[j] = dp[j - 1] + triangle[i][j];

                }

                else if(j == 0)

                {

                    dp[j] = dp[j] + triangle[i][j];

                }

                else

                {

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

                }

            }

        }

        int MIN = dp[0];

        for(int i = 1; i < len; i++)

        {

            MIN = min(MIN, dp[i]);

        }

        return MIN;

    }

};

巴特西

Leetcode120.Triangle三角形最小路径和

最新文章

热门文章