首页 > > 程序设计 > C/C++ >

lintcode 109 数字三角形

2018-06-17 21:44:21来源：未知阅读 ()

数字三角形

描述
笔记
数据
评测

给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。

注意事项

如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数。

您在真实的面试中是否遇到过这个题？

Yes

哪家公司问你的这个题？ LinkedIn Amazon Airbnb Cryptic Studios Dropbox Epic Systems TinyCo Hedvig Uber Yelp Apple Yahoo Bloomberg Zenefits Twitter Microsoft Google Snapchat Facebook

感谢您的反馈

样例

比如，给出下列数字三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。

标签

动态规划

相关题目

class Solution {
public:
    /*
     * @param triangle: a list of lists of integers
     * @return: An integer, minimum path sum
     */
    
    int minimumTotal(vector<vector<int>> &triangle) {
        // write your code here
        int x=triangle.size();
        int y=triangle[x-1].size();
        for(int i=x-2;i>=0;i--){
            for(int j=0;j<=i;j++){
                triangle[i][j]=min(triangle[i+1][j],triangle[i+1][j+1])+triangle[i][j];
            }
        }
        return triangle[0][0];
    }
    
};

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有