`
cozilla
  • 浏览: 91905 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

[Leetcode] Triangle

 
阅读更多
TriangleOct 30 '126503 / 17796

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.

 

 

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        int n = triangle.size();
        if (n == 0) return 0;
        vector<int> res(n);
        res[0] = triangle[0][0];
        for (int i = 1; i < n; i++) {
            res[i] = res[i-1] + triangle[i][i];
            for (int j = i - 1; j > 0; j--) {
                res[j] = min(res[j-1], res[j]) + triangle[i][j]; 
            }
            res[0] += triangle[i][0];
        }
        int x =res[0];
        for (int i = 1; i < n; i++) 
            if (x > res[i]) x = res[i];
        return x;
    }
};

 

分享到:
评论

相关推荐

    python-leetcode题解之120-Triangle

    python python_leetcode题解之120_Triangle

    java-leetcode题解之Largest Triangle Area.java

    java java_leetcode题解之Largest Triangle Area.java

    js-leetcode题解之120-triangle.js

    javascript js_leetcode题解之120-triangle.js

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...

    python-leetcode题解之118-Pascal's-Triangle

    python python_leetcode题解之118_Pascal's_Triangle

    python-leetcode题解之119-Pascal's-Triangle-II

    python python_leetcode题解之119_Pascal's_Triangle_II

    js-leetcode题解之118-pascal's-triangle.js

    javascript js_leetcode题解之118-pascal's-triangle.js

    LeetCode-Triangle

    《LeetCode-Triangle:深入解析Java解题策略》 在编程世界中,LeetCode是一个备受推崇的在线平台,它提供了一系列的算法题目,帮助开发者提升编程技能和算法理解能力。"Triangle"是LeetCode中的一道经典问题,涉及...

    js-leetcode题解之119-pascal's-triangle-II.js

    javascript js_leetcode题解之119-pascal's-triangle-II.js

    Leetcode题目+解析+思路+答案.pdf

    - **Pascal's Triangle**:生成帕斯卡三角形的某一行。 - **Merge Sorted Array**:合并两个已排序的数组,使合并后的数组仍然有序。 - **Sum**:计算数组的总和。 - **Find Minimum in Rotated Sorted Array**...

    LeetCode leetcode部分题解答代码实现

    * Pascal's Triangle:给定一个整数 n,返回帕斯卡三角形的前 n 行。这个题目需要使用动态规划的思想,首先初始化一个二维数组,然后遍历数组,并将每个元素设置为其左上和右上的和。 * Merge Sorted Array:给定两...

    Java-Leetcode-杨辉三角.zip

    在IT领域,尤其是在编程和算法学习中,LeetCode是一个非常受欢迎的在线平台,它提供了大量的编程挑战题目,帮助开发者提升技能并准备面试。本压缩包“Java-Leetcode-杨辉三角.zip”显然聚焦于Java语言解决LeetCode上...

    LeetCode C++全解

    Pascal's Triangle v. Merge Sorted Array vi. Sum vii. Find Minimum in Rotated Sorted Array viii. Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. ...

    php-leetcode题解之三角形最小路径和.zip

    LeetCode是一个在线平台,提供各种编程题目,帮助程序员提升算法技能,而这个题目就是其中的一个经典问题。 三角形最小路径和的问题描述如下:给定一个三角形,每个顶点都有一个非负整数,目标是找到一条从顶部到...

    leetcode卡-leetcode_python:leetcode_python

    Triangle 2020-01-15 213 House Robberll -变种 198 337 2020-01-16 139 单词拆分 2020-01-20 104 树 -变种 111 2020-01-21 129 Sum root to leaf numbers 2020-01-22 226 翻转二叉树 2020-01-23 95 不同的二叉搜索...

    python-leetcode面试题解之第118题杨辉三角-题解.zip

    LeetCode是一个在线平台,它提供了大量的编程题目,旨在帮助程序员提升算法能力和技术实力,尤其对于准备求职面试的开发者来说,LeetCode是不可或缺的资源。本题解将深入探讨LeetCode中的第118题——“杨辉三角”。 ...

    gasstationleetcode-LeetCode_Practice:我的LeetCode练习从2020年开始

    leetcode 力扣_实践 标签: leetcode 我的 LeetCode 练习从 2020 年开始 前言 尝试将 Leetcode 作为我的日常练习。 将更新带有解释的解决方案。 大批 27_Remove_element 26_Remove_Duplicates 80_Remove_Duplicates_...

    python-leetcode面试题解之第120题三角形最小路径和-题解.zip

    在本压缩包中,我们关注的是一个Python编程与算法相关的面试题目——LeetCode的第120题,名为“三角形最小路径和”。这是一道经典的动态规划问题,经常出现在IT行业的求职面试中,尤其是对于那些希望在软件开发或者...

    基于Java实现杨辉三角 LeetCode Pascal's Triangle

    这段代码展示了如何用Java编程语言有效地解决LeetCode上的Pascal's Triangle问题。它利用了杨辉三角的递归性质,通过迭代而非递归的方式降低了复杂性,使得算法的效率更高。同时,代码结构清晰,易于理解,是学习...

    leetcode答案-leetcode:每日三题

    Triangle Given two sorted integer arrays A and B, merge B into A as one sorted array.Note: You may assume that A has enough space (size that is greater or equal to m + n)to hold additional elements ...

Global site tag (gtag.js) - Google Analytics