TriangleOct 30 '12
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.
dp
class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { int s = triangle.size(); if (s == 0)return 0; int *a = new int[s]; memset(a, 0, 4*s); a[0] = triangle[0][0]; for (int i = 1; i < triangle.size(); ++i) { a[triangle[i].size() - 1] = a[triangle[i].size()-2] + triangle[i][triangle[i].size()-1]; for (int j = triangle[i].size()-2; j >=1; --j) { a[j] = min(a[j-1], a[j]) + triangle[i][j]; } a[0] += triangle[i][0]; } int res = a[0]; for (int i = 1; i < s; i++) { if (res > a[i]) res = a[i]; } delete []a; return res; } };
相关推荐
LeetCode-Triangle
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
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. ...
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 不同的二叉搜索...
主要介绍了基于Java实现杨辉三角 LeetCode Pascal's Triangle的相关资料,需要的朋友可以参考下
leetcode 力扣_实践 标签: leetcode 我的 LeetCode 练习从 2020 年开始 前言 尝试将 Leetcode 作为我的日常练习。 将更新带有解释的解决方案。 大批 27_Remove_element 26_Remove_Duplicates 80_Remove_Duplicates_...
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 ...
leetcode lintcode差异 leetcode-python 九章算法基础班 二分 题目 地址 153. Find Minimum in Rotated Sorted Array 双指针 题目 Solution Tag LintCode 604. Window Sum LeetCode 283. Moves Zeroes Array、Two ...
leetcode 分类 LeetCode Progress ...Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
2sum leetcode leetcode 文件和描述 removeelement.cpp,删除特定元素 ...triangle.cpp,动态方法从三角形中找到从上到下的最小路径总和 maxsubarray.cpp,动态方法从数组中找到连续子数组的最大和
leetcode 2 sum c Leetcode 练习记录 这个专案主要存放我练习Leetcode有针对难度分类的集合题库(Collection Question) 准备方式 分析tag的热门标签,熟悉各个标签解题的思路(解决该标签全部的easy和medium为主),再...
leetcode========leetcode 题解,更新中.提供Java和 Python 版本的solution为了让更多的同学了解并应用Leetcode,代码...简单数学:http://oj.leetcode.com/problems/pascals-triangle/http://oj.leetcode.com/proble
leetcode添加元素使和等于 leetCode 递归 95 能够想到用递归左右产生子树的方法,但是程序就是写不出来,主要在于对于一个root i, 要实现左右子树的所有情况,左右子树是独立的, 添加两层循环,把左右子树的各种...
# Modify the original triangle, bottom-up def minimumTotal(self, triangle): """ :type triangle: List[List[int]] :rtype: int """ if not triangle: return for i in range(len(triangle) - 2, -
leetcode双人赛 leetcode-solution 闲暇之余,刷一下题,弥补数据结构和算法的短板 概述 之前写过一个 leetcode 的一点题解,不过后来就断了,现在重新开个项目:party_popper::party...pascals-triangle 杨辉三角 II pa
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
leetcode-js Leecode 经典题目 JavaScript TypeScript 题解。 Leetcode's answers by JavaScript and TypeScript. easy 66.加一 (Plus One) 67.二进制求和 (Add Binary) 69.x 的平方根 (Sqrt(x)) 70.爬楼梯 ...
java lru leetcode leetcode HashMap问题 滑动窗口问题 ...Math.min(dp[i-1][j-1],dp[i-1][j]+triangle[i][j]) dp[i] += dp[i-j]*dp[j-1]) dp[i][j]=dp[i-1][j]+dp[i][j-1]) dp[i]=Math.max(dp[i-1],dp[i-2
Triangle (杨辉三角) 124 二叉树最大路径和 136 x ^ x = 0 169 Majority Vote Algorithm (最大投票数算法) 240 检索二阶矩阵 189 数组操作的时间复杂度比较 206 反转单向链表 226 反转二叉树 459 重复子字符串模式...
leetcode 在牛客网上的在线编程中的leetcode在线编程题解 代码中有详细题解 完成: 树 Minimum Depth of Binary Tree 栈 evaluate-reverse-polish-notation 链表 sort-list 排序 insertion-sort-list 树 binary-tree...