leetcode-120-Triangle-等腰三角形

MarvinZhang 发布于2019-07-30 16:07 / 1490人阅读

摘要：题目示例题目解析此题是等腰三角形，上下之间的关系简化为上下相邻的三个数，相邻，大小关系是在下方二选一上方的数值，必然正确。根据此思路，可以或者，由于可以简化，所以动态规划方法。代码普通代码，较慢动态规划，简练

题目：

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

示例：

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

题目解析：

1.此题是等腰三角形，上下之间的关系简化为上下相邻的三个数，index相邻，大小关系是在下方二选一+上方的数值，必然正确。 根据此思路，可以top-bottom,或者bottom-top，由于可以简化，所以动态规划方法。   
2. 采用bottom-top方法，最后简化为1个值，所以左侧值放置两值中的小值。

代码：

普通代码，较慢：
class Solution_:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        all_paths=[]
        cur_path=[triangle[0][0]]
        # cur_path=[]
        cur_index=[0,0]
        self.bfs(all_paths,cur_path,cur_index,triangle)
        print(all_paths)
        sums=[sum(elem) for elem in all_paths]
        return min(sums)
    def bfs(self,all_paths,cur_path,cur_index,triangle):
        x_cur=cur_index[0]
        # cur_row=triangle[x_cur]
        x_threshold=len(triangle)
        y_cur=cur_index[1]
        x_next=x_cur+1
        y_next=[]
        if x_next=0:
            y_next.append(y_cur)
            if y_cur+1

云服务器 GPU云服务器等腰三角形三角形等边三角形三角形面积

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

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

[LeetCode] 120. Triangle

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], ...

stormjun 2019-08-16 13:51 评论0 收藏0
【基础】在CSS中绘制三角形及相关应用

摘要：基本原理在中，我们可以利用四个属性来绘制三角形。绘制三角形等边三角形等边三角形又称正三边形，为三边相等的三角形，其三个内角相等，均为，它是锐角三角形的一种。简言本文简要阐述了用CSS边框的方法在页面上绘制三角形，包括几种典型的三角形绘制，还介绍了几个简单的应用场景。利用边框绘制三角形方法只是众多方案中的一种，大家根据项目实际，选用最适宜项目的方案。 showImg(https://...

Lycheeee 2019-08-30 15:53 评论0 收藏0
CSS实现空心三角指示箭头

摘要：开发中，三角形的日常应用，以三角形指示箭头最为常见，其用来实现非常简单，熟悉了之后相比于引入或是背景图片会是更好更灵活的选择。这样就实现三角形了。实心三角形箭头实心三角形的原理就是一个三角形绝对定位到主体元素边界处并连接起来。 web开发中，三角形的日常应用，以三角形指示箭头最为常见，其用CSS来实现非常简单，熟悉了之后相比于引入SVG或是背景图片会是更好更灵活的选择。而三角箭头一般...

makeFoxPlay 2019-08-30 15:53 评论0 收藏0
利用js实现等腰三角形

摘要：等腰三角形主要是利用中的循环考验对循环的灵活运用还有就是利用空格来调位置，来实现等腰三角形的排列。等腰三角形主要是利用js中的for循环考验对for循环的灵活运用还有就是利用空格来调*位置，来实现等腰三角形的排列。 for (var h = 9 - 1; h >= i; h--) { //打印等腰三角形每行前的空格数(大循环内的第一个循环) ...

lscho 2019-08-29 16:28 评论0 收藏0
利用js实现等腰三角形

摘要：等腰三角形主要是利用中的循环考验对循环的灵活运用还有就是利用空格来调位置，来实现等腰三角形的排列。等腰三角形主要是利用js中的for循环考验对for循环的灵活运用还有就是利用空格来调*位置，来实现等腰三角形的排列。 for (var h = 9 - 1; h >= i; h--) { //打印等腰三角形每行前的空格数(大循环内的第一个循环) ...

maxmin 2019-08-26 12:19 评论0 收藏0