【题目】
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.
【分析】
这是一道动态规划的题目,求一个三角形二维数组从顶到低端的最小路径和。
我们从低端向顶端计算。设状态为 S[i][j]表示从从位置 ( i, j ) 出发,到最低端路径的最小和
状态转移方程:
S[i][j] = min(S[i+1][j] + S[i+1][j+1]) +S[i][j]
S[0][0]就是要求解的答案。
时间复杂度 O(n^2) ,空间复杂度 O(1)
【代码】
/**------------------------------------
* 日期:2015-02-03
* 作者:SJF0115
* 题目: 120.Triangle
* 网址:https://oj.leetcode.com/problems/triangle/
* 结果:AC
* 来源:LeetCode
* 博客:
---------------------------------------**/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
int size = triangle.size();
// down-to-top
// 第i层
for(int i = size - 2;i >= 0;--i){
// 第i层的第j个元素
for(int j = 0;j <= i;++j){
triangle[i][j] += min(triangle[i+1][j],triangle[i+1][j+1]);
}//for
}//for
return triangle[0][0];
}
};
int main(){
Solution s;
vector<vector<int> > triangle = {{2},{3,4},{6,5,3},{4,1,8,3}};
int result = s.minimumTotal(triangle);
// 输出
cout<<result<<endl;
return 0;
}
【思路二】
一位网友说:虽然是O(1)的空间复杂度,但其实破坏了三角形本身啊。如果算上占用的三角形本身的空间,实际使用的空间复杂度应该算O(N^2)了。
只求值不求本身的时候,都是可以用空间轮转这个办法的。如LCS、走棋盘等等一批问题,都可以这么节省。
从上面思路的状态转移方程中看出:S[i][j] = min(S[i+1][j] + S[i+1][j+1]) +S[i][j]
S[i][j]只与下一行的第j个元素和第j+1个元素相关,i的关系是固定的,因此我们可以省去这一维。
开辟O(N)的数组,然后规划的时候使用S[j] = min(S[j+1], S[j) +Triangle[i][j]就可以了。
【代码二】
/*------------------------------------
* 日期:2015-02-03
* 作者:SJF0115
* 题目: 120.Triangle
* 网址:https://oj.leetcode.com/problems/triangle/
* 结果:AC
* 来源:LeetCode
* 博客:
---------------------------------------*/
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
int size = triangle.size();
vector<int> next(triangle.back());
// down-to-top
// 第i层
for(int i = size - 2;i >= 0;--i){
// 第i层的第j个元素
for(int j = 0;j <= i;++j){
next[j] = min(next[j],next[j+1]) + triangle[i][j];
}//for
}//for
return next[0];
}
};
分享到:
相关推荐
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
# 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, -
120. Triangle LintCode 382. Triangle Count/LeetCode 611. Valid Triangle Number LeetCode 18. 4Sum (LeetCode 86. Partition List) LintCode 373. Partition Array by Odd and Even Mock Interview 题目 ...
加油站 leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 ...120.Triangle, 139.Word Break, 152.Maximum Produ
leetcode========leetcode 题解,更新中.提供Java和 Python 版本的solution为了让更多的同学了解并应用Leetcode,代码注释尽可能的...http://oj.leetcode.com/problems/pascals-triangle/http://oj.leetcode.com/proble
LeetCode-Triangle
主要介绍了基于Java实现杨辉三角 LeetCode Pascal's Triangle的相关资料,需要的朋友可以参考下
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. ...
120 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 不同的二叉...
题目 给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中...链接:https://leetcode-cn.com/problems/triangle 思路 题目要求每一步只能移动到下一行中相邻的节点上。比如3只能移动到6或5;4只能移
2sum leetcode leetcode 文件和描述 removeelement.cpp,删除特定元素 ...triangle.cpp,动态方法从三角形中找到从上到下的最小路径总和 maxsubarray.cpp,动态方法从数组中找到连续子数组的最大和
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添加元素使和等于 leetCode 递归 95 能够想到用递归左右产生子树的方法,但是程序就是写不出来,主要在于对于一个root i, 要实现左右子树的所有情况,左右子树是独立的, 添加两层循环,把左右子树...triangle.
leetcode-js Leecode 经典题目 JavaScript TypeScript 题解。 Leetcode's answers by JavaScript and TypeScript. easy 66.加一 (Plus One) 67.二进制求和 (Add Binary) 69.x 的平方根 (Sqrt(x)) 70.爬楼梯 ...
leetcode 刷题笔记 记录一些刷题细节,很惭愧只做了一点微小的工作 4.13 162题. Find Peak Element.Binary search,需要比较nums[mid]和nums[mid+1]. 4.12 212题. Word Search II. 用trie tree存word list,然后dfs. ...
圆和椭圆重叠leetcode ——#158 尖端 关心特殊情况 从不同的方向思考 简单的 大批 1.Two Sum -> 使用哈希表避免遍历列表448.查找数组中消失的所有数字-> 1.建立缓冲区来计算数字| 2.使用数组作为带符号的缓冲区118....
leetcode 分类 LeetCode Progress ...Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
leetcode 2 sum c Leetcode 练习记录 这个专案主要存放我练习Leetcode有针对难度分类的集合题库(Collection Question) 准备方式 分析tag的热门标签,熟悉各个标签解题的思路(解决该标签全部的easy和medium为主),再...
leetcode双人赛 leetcode-solution 闲暇之余,刷一下题,弥补数据结构和算法的短板 概述 之前写过一个 leetcode 的一点题解,不过后来就断了,现在重新开个项目:party_popper::party...pascals-triangle 杨辉三角 II pa