[LeetCode] 120. Triangle

stormjun 发布于2019-08-16 13:51 / 1475人阅读

Problem

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.

Bottom-top DP

class Solution {
    public int minimumTotal(List> triangle) {
        int[] dp = new int[triangle.size()+1];
        for (int i = triangle.size()-1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}

Non Extra Space DP

class Solution {
    public int minimumTotal(List> triangle) {
        int len = triangle.size();
        for (int i = len-2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                int preMin = Math.min(triangle.get(i+1).get(j), triangle.get(i+1).get(j+1));
                int curMin = preMin + triangle.get(i).get(j);
                triangle.get(i).set(j, curMin);
            }
        }
        return triangle.get(0).get(0);
    }
}

idc机房托管专线服务 Triangle LeetCode pascal_triangle 120美金

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72458.html

leetcode-120-Triangle-等腰三角形

摘要：题目示例题目解析此题是等腰三角形，上下之间的关系简化为上下相邻的三个数，相邻，大小关系是在下方二选一上方的数值，必然正确。根据此思路，可以或者，由于可以简化，所以动态规划方法。代码普通代码，较慢动态规划，简练题目： Given a triangle, find the minimum path sum from top to bottom. Each step you may mov...

MarvinZhang 2019-07-30 16:07 评论0 收藏0
[Leetcode] Triangle 三角形

摘要：动态规划复杂度时间空间思路这题我们可以从上往下依次计算每个节点的最短路径，也可以自下而上。自下而上要简单一些，因为我们只用在两个下方元素中选一个较小的，就能得到确定解。 Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent ...

jayce 2019-08-14 12:23 评论0 收藏0
[LintCode/LeetCode] Triangle

摘要：第一种方法是很早之前写的，先对三角形两条斜边赋值，和分别等于两条斜边上一个点的和与当前点的和。然后套用动规公式进行横纵坐标的循环计算所有点的，再遍历最后一行的，找到最小值即可。 Problem Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacen...

刘德刚 2019-08-14 15:28 评论0 收藏0
css绘制各种形状图形（第二版）

摘要：虽然我们现在大都使用字体图标或者图片，似乎使用来做图标意义不是很大，但怎么实现这些图标用到的一些技巧及思路是很值得我们的学习。虽然我们现在大都使用字体图标或者svg图片，似乎使用 CSS 来做图标意义不是很大，但怎么实现这些图标用到的一些技巧及思路是很值得我们的学习。一、实心圆 showImg(https://segmentfault.com/img/bVbsV6v?w=171&h...

CoreDump 2019-08-30 10:58 评论0 收藏0