[Leetcode] Triangle 三角形

jayce 发布于2019-08-14 12:23 / 2094人阅读

摘要：动态规划复杂度时间空间思路这题我们可以从上往下依次计算每个节点的最短路径，也可以自下而上。自下而上要简单一些，因为我们只用在两个下方元素中选一个较小的，就能得到确定解。

Triangle

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).

动态规划 复杂度

时间 O(NM) 空间 O(1)

思路

这题我们可以从上往下依次计算每个节点的最短路径，也可以自下而上。自下而上要简单一些，因为我们只用在两个下方元素中选一个较小的，就能得到确定解。如果将上一层的累加和存在一个一维数组里，则可以只用O(n)空间，但实际上我们可以直接in place在输入list中修改值，就可以不用额外空间了。

代码

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

专线服务 idc机房托管 Triangle LeetCode pascal_triangle LeetCode_String

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

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

leetcode # 118:Pascal's Triangle 杨辉三角

摘要：杨辉三角给定一个非负整数，生成杨辉三角的前行。在杨辉三角中，每个数是它左上方和右上方的数的和。另外可以在内层循环加判断在不等于时才加上，这样可省略代码段，但是这个会在每次进入第一次循环后判断一次。本着减少资源消耗的原则，应当提到外面。 118:Pascals Triangle 杨辉三角 Given a non-negative integer numRows, generate the...

CKJOKER 2019-07-31 10:37 评论0 收藏0
leetcode # 118:Pascal's Triangle 杨辉三角

摘要：杨辉三角给定一个非负整数，生成杨辉三角的前行。在杨辉三角中，每个数是它左上方和右上方的数的和。另外可以在内层循环加判断在不等于时才加上，这样可省略代码段，但是这个会在每次进入第一次循环后判断一次。本着减少资源消耗的原则，应当提到外面。 118:Pascals Triangle 杨辉三角 Given a non-negative integer numRows, generate the...

gggggggbong 2019-08-16 18:23 评论0 收藏0
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] Pascal's Triangle 杨辉三角形

摘要：迭代法复杂度时间空间思路简单的按照杨辉三角形的规则计算就行了。代码加入第一个加入中间的数加入最后一个逆序相加法复杂度时间空间思路同样用迭代的方法，根据上一层的值算下一层，不过这里每一层都在同一个上操作。 Pascals Triangle I Given numRows, generate the first numRows of Pascals triangle. For examp...

Berwin 2019-08-14 12:37 评论0 收藏0
LeetCode 118：杨辉三角 II Pascal's Triangle II

摘要：公众号爱写作者爱写给定一个非负索引，其中，返回杨辉三角的第行。在杨辉三角中，每个数是它左上方和右上方的数的和。示例输入输出进阶你可以优化你的算法到空间复杂度吗解题思路和之前写的那篇号杨辉三角基本类似。公众号：爱写bug（ID：icodebugs）作者：爱写bug 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。 Given a non-negative index...

KaltZK 2019-08-16 18:29 评论0 收藏0