关关的刷题日记96 – Leetcode 120. Triangle

关关的刷题日记96 – Leetcode 120. 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).

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.

给定一个三角形,找到从顶端到低端的最小路径和。每一次可以移动到下一排的相邻的数。能否实现只需要O(n)空间复杂度的算法,n为三角的行数。

思路

对于每一个点来说,以其为端点的路径要么是从左上点下来的,要么是从右上点下来的,所以以这点为端点的路径和sum[i][j]=min(sum[i-1][j-1], sum[i-1][j])+这点值,采用动规的方法来做。

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

人生易老,唯有陪伴最长情,加油!

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2018-01-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏james大数据架构

算法系列

  算法对程序员来说是熟悉的陌生人,编过大量代码后突然被哪个问到算法是什么也有时不知从何说起,简单来说是没有好好总结过仔细分析过。大学里面导师整天苦口婆心的教导...

237100
来自专栏专知

【LeetCode 383】关关的刷题日记41 – Leetcode 383. Ransom Note

关关的刷题日记41 – Leetcode 383. Ransom Note 题目 Given an arbitrary ransom note string a...

36760
来自专栏专知

关关的刷题日记79 – Leetcode 9 Palindrome Number

关关的刷题日记79 – Leetcode 9 Palindrome Number 题目 Determine whether an integer is a pa...

37080
来自专栏一个会写诗的程序员的博客

编程范式 (Programming paradigm)

范,模范、典范也。范式即模式、方法。常见的编程范式有:函数式编程、程序编程、面向对象编程、指令式编程等。

36610
来自专栏Aloys的开发之路

关于强制式(命令式)语言和声明式语言的区别

在阅读Alfred V.Aho等的大作Compilers Principles,Techniques and Tools是看到如下一段话: Another  c...

30150
来自专栏专知

关关的刷题日记07——Leetcode 26. Remove Duplicates from Sorted Array 方法1

关小刷刷题07 – Leetcode 26. Remove Duplicates from Sorted Array 方法1 题目 Given a sorted...

30140
来自专栏Web行业观察

盘点那些奇形怪状的编程语言

有的语言是多面手,在很多不同的领域都能派上用场。这类编程语言叫 general-purpose language,简称 GPL。大家学过的编程语言很多都属于这一...

30320
来自专栏数据结构与算法

1095 火星人

1095 火星人 2004年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 D...

366100
来自专栏专知

【LeetCode 136】 关关的刷题日记32 Single Number

关关的刷题日记32 – Leetcode 136. Single Number 题目 Given an array of integers, every ele...

35460
来自专栏专知

【LeetCode 409】 关关的刷题日记31Longest Palindrome

关关的刷题日记31 – Leetcode 409. Longest Palindrome 题目 Given a string which consists o...

28430

扫码关注云+社区

领取腾讯云代金券