【学习笔录】每周一道算法题：三角形最小路径和

Author： YH_evIs
发布时间：December 9, 2019
25286views
One comment
600字数
Categories：算法

##上周回顾##
<div class="preview">
<div class="post-inser post box-shadow-wrap-normal">
<a href="https://yhevis.top/index.php/archives/56/" target="_blank" class="post_inser_a ">
<div class="inner-image bg" style="background-image: url(https://yhevis.top/usr/themes/handsome/assets/img/sj/5.jpg);background-size: cover;"></div>

<div class="inner-content" >
<p class="inser-title">【学习笔录】每周一道算法题：串联字串</p>
<div class="inster-summary text-muted">
题目给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的...
</div>
</div>
</a>

</div>

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

例如，给定三角形：
```javascript
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
```
自顶向下的最小路径和为 11（即，**2** + **3** + **5** + **1** = 11）。

**说明：**

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
##解答##
```javascript
var minimumTotal = function(triangle) {
for(var i = triangle.length-2;i >= 0;i--){
for(var j = 0;j < triangle[i].length;j++){
triangle[i][j] = Math.min(triangle[i+1][j],triangle[i+1][j+1]) + triangle[i][j];
}
}
return triangle[0][0];
};
```

Last modification：December 16th, 2019 at 03:11 pm

如果觉得我的文章对你有用，请随意赞赏

One comment

两仪橙

December 16th, 2019 at 02:45 pm

试着使用了JS，写的不好的地方指点下~

var rec = [
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
var res = [];
res.push(rec[0][0]);
while(res.length !== rec.length){
    res.unshift(res[0]+rec[res.length][0]);
    for(var i = 1; i < res.length-1; i++){
        res[i] = Math.min(res[i]+rec[res.length-1][i], res[i+1]+rec[res.length-1][i]);
    }
    res[res.length-1] += rec[res.length-1][res.length-1];
}
res.sort()
console.log(res[0]);