LeetCode
  • Introduction
  • 第一章: 基本结构
    • 1.1 数组
      • Q11. Container With Most Water
      • Q16. 3Sum Closest
      • Q118. Pascal's Triangle
      • Q119. Pascal's Triangle II
      • Q120. Triangle
      • Q134. Gas Station
    • 1.2 链表
      • Q2: Add Two Numbers
      • Q19. Remove Nth Node From End of List
      • Q82. Remove Duplicates from Sorted List II
      • Q86: Partition List
      • Q92. Reverse Linked List II
      • Q141. Linked List Cycle
      • Q142. Linked List Cycle II
      • Q147. Insertion Sort List
      • Q160. Intersection of Two Linked Lists
      • Q206. Reverse Linked List
    • 1.3 哈希
      • Q1: Two Sum
      • Q3. Longest Substring Without Repeating Characters
    • 1.4 堆栈
      • Q84: Largest Rectangle in Histogram
      • Q155. Min Stack
      • Q20. Valid Parentheses
      • Q225. Implement Stack using Queues
      • Q232. Implement Queue using Stacks
    • 1.5 树
      • Q94. Binary Tree Inorder Traversal
      • Q100. Same Tree
      • Q101. Symmetric Tree
      • Q102. Binary Tree Level Order Traversal
      • Q103. Binary Tree Zigzag Level Order Traversal
      • Q104. Maximum Depth of Binary Tree
      • Q105. Construct Binary Tree from Preorder and Inorder Traversal
      • Q106. Construct Binary Tree from Inorder and Postorder Traversal
      • Q107. Binary Tree Level Order Traversal II
      • Q108. Convert Sorted Array to Binary Search Tree
      • Q109. Convert Sorted List to Binary Search Tree
      • Q110. Balanced Binary Tree
      • Q111. Minimum Depth of Binary Tree
      • Q112. Path Sum
      • Q113. Path Sum II
      • Q114. Flatten Binary Tree to Linked List
      • Q116. Populating Next Right Pointers in Each Node
      • Q117. Populating Next Right Pointers in Each Node II
      • Q129. Sum Root to Leaf Numbers
      • Q144. Binary Tree Preorder Traversal
    • 1.6 图
    • 1.7 二进制
      • Q89. Gray Code
      • Q136. Single Number
      • Q137. Single Number II
      • Q191. Number of 1 Bits
      • Q190. Reverse Bits
    • 1.8 字符串
      • Q5. Longest Palindromic Substring
      • Q14. Longest Common Prefix
      • Q125. Valid Palindrome
  • 第二章: 动态规划
    • Q85: Maximal Rectangle
    • Q91. Decode Ways
    • Q121. Best Time to Buy and Sell Stock
    • Q198. House Robber
  • 第三章: 递归
    • Q17. Letter Combinations of a Phone Number
    • Q78. Subsets
    • Q86. Scramble String
    • Q90: Subsets II
  • 第四章:贪心
    • Q122. Best Time to Buy and Sell Stock II
  • 第五章:分治法
  • 第六章:数学
    • Q6. ZigZag Conversion
    • Q7. Reverse Integer
    • Q9. Palindrome Number
    • Q168. Excel Sheet Column Title
    • Q171. Excel Sheet Column Number
  • 第七章:查找
    • Q15. Three Sum
    • Q167. Two Sum II
    • Q169. Majority Element
  • 第八章:排序
Powered by GitBook
On this page
  • 分析
  • C++代码

Was this helpful?

  1. 第一章: 基本结构
  2. 1.1 数组

Q120. Triangle

PreviousQ119. Pascal's Triangle IINextQ134. Gas Station

Last updated 5 years ago

Was this helpful?

直达:

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 is11(i.e.,2+3+5+1= 11).

Note: Bonus point if you are able to do this using onlyO(n) extra space, wherenis the total number of rows in the triangle.

分析

算法思路类似于Q119, 不同之处在于矩阵的更新方法,由求和变成求最小值。

C++代码

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.size() == 0) return 0;
        vector<int> res(triangle.size(), 0);
        for(int i = 0; i<triangle.size(); i++){
            if(i == 0) res[0] = triangle[0][0];
            else{
                for(int j=i;j>=0;j--){
                    if(j == i) res[j] = triangle[i][j] + res[j-1];
                    else if(j == 0) res[j] = triangle[i][j] + res[j];
                    else res[j] = min(res[j], res[j-1]) + triangle[i][j];
                }
            }
        }
        int min_res = res[0];
        for(int k = 0; k<res.size(); k++){
            min_res = min(res[k], min_res);
        }
        return min_res;
    }
};
https://leetcode.com/problems/triangle/description/