问题描述:
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.
原问题链接:https://leetcode.com/problems/triangle/
问题分析
这个问题要找到合理的思路还是有点麻烦的。对于前面问题的描述中,我们需要看这么一个规律。给定的第几行,那么这一行就有几个元素。而这里还有一个要求就是对于上面一行的元素来说,它可以和它下一行同一个索引位置以及一个相邻位置的元素相加。所以对于前一行第i个位置的元素来说,它可以和下一行里的i - 1, i, i + 1位置的元素选择相加。对于每个相加后有重叠位置的元素,我们取更小的那个元素设置为它们相加后选的值。
按照这个思路,我们在实现的时候,每次要创建一个比前一行长度大一的数组,然后通过比较每个元素和它周边的值来求的下一行的值。这个值将作为计算下一行值的基础。就这样一直到最后一行。我们最后从得到的数组里找出最小的那个元素。这个思路虽然可行,但是我们的空间使用情况超出了O(n)的限制。因为每次加一的申请空间,我们的空间使用情况甚至达到了0(n x n)的情况。
看来,我们要寻找新的思路。在上面的思路里,我们之所以申请的空间超出了限制,是因为每次没法重用前面依次申请的数组。因为每次要创建的数组长度要加一。如果我们一开始就创建一个长度为n的数组的话,我们需要控制每一次它遍历所能访问的长度限制。这样会比较麻烦。
不过如果我们转换一下思路,比如说,我们从最后一行开始向上面一行每次这么比较累加的话呢?我们可以申请一个和最后一行长度一样的数组,把最后一行的值赋给这个数组。而要求它上一行数组元素的时候,我们可以得到一个这样的关系:
minLen[i] = Math.min(minLen[i], minLen[i + 1]) + triangle.get(layer).get(i)。其中layer表示当前所在的层。这种不断收缩的方式可以使得代码更加简洁。我们最终返回的结果里只需要返回minLen[0]就可以了。
这样,我们可以得到详细的实现代码如下:
public class Solution { public int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); int[] minLen = new int[n]; for(int i = 0; i < triangle.get(n - 1).size(); i++) minLen[i] = triangle.get(n - 1).get(i); for(int layer = n - 2; layer >= 0; layer--) { for(int i = 0; i <= layer; i++) { minLen[i] = Math.min(minLen[i], minLen[i + 1]) + triangle.get(layer).get(i); } } return minLen[0]; } }
相关推荐
2sum leetcode leetcode 文件和描述 removeelement.cpp,删除特定元素 ...triangle.cpp,动态方法从三角形中找到从上到下的最小路径总和 maxsubarray.cpp,动态方法从数组中找到连续子数组的最大和
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 Progress ...Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
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
leetcode添加元素使和等于 leetCode 递归 95 能够想到用递归左右产生子树的方法,但是程序就是写不出来,主要在于对于一个root i, 要实现左右子树的所有情况,左右子树是独立的, 添加两层循环,把左右子树的各种...
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/...
Triangle (杨辉三角) 124 二叉树最大路径和 136 x ^ x = 0 169 Majority Vote Algorithm (最大投票数算法) 240 检索二阶矩阵 189 数组操作的时间复杂度比较 206 反转单向链表 226 反转二叉树 459 重复子字符串模式...
leetcode添加元素使和等于 Leetcode Part1 共55道 1 plusOne easy 描述:用一组数据表示一个整数,实现整数加一的操作 主要思路:主要考虑最高位进位的情况,可以创建一个长度加一的数组,原数组...Triangle II easy 描
LeetCode-Triangle
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
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 不同的二叉搜索...
leetcode 力扣_实践 标签: leetcode 我的 LeetCode 练习从 2020 年开始 前言 尝试将 Leetcode 作为我的日常练习。 将更新带有解释的解决方案。 大批 27_Remove_element 26_Remove_Duplicates 80_Remove_Duplicates_...
leetcode========leetcode 题解,更新中.提供Java和 Python 版本的solution为了让更多的同学了解并应用Leetcode,代码...简单数学:http://oj.leetcode.com/problems/pascals-triangle/http://oj.leetcode.com/proble
leetcode lintcode差异 leetcode-python 九章算法基础班 二分 题目 地址 153. Find Minimum in Rotated Sorted Array 双指针 题目 Solution Tag LintCode 604. Window Sum LeetCode 283. Moves Zeroes Array、Two ...
圆和椭圆重叠leetcode ——#158 尖端 关心特殊情况 从不同的方向思考 简单的 大批 1.Two Sum -> 使用哈希表避免遍历列表448.查找数组中消失的所有数字-> 1.建立缓冲区来计算数字| 2.使用数组作为带符号的缓冲区118....
leetcode 2 sum c Leetcode 练习记录 这个专案主要存放我练习Leetcode有针对难度分类的集合题库(Collection Question) 准备方式 分析tag的热门标签,熟悉各个标签解题的思路(解决该标签全部的easy和medium为主),再...
leetcode双人赛 leetcode-solution 闲暇之余,刷一下题,弥补数据结构和算法的短板 概述 之前写过一个 leetcode 的一点题解,不过后来就断了,现在重新开个项目:party_popper::party...pascals-triangle 杨辉三角 II pa
颜色分类leetcode 形状 :blue_circle: :large_orange_diamond: :red_triangle_pointed_up: :red_circle: 一个示例数据集生成器,用于在使用真实世界的数据集进行测试之前,对计算机视觉模型进行分类、检测和分割试验...
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-js Leecode 经典题目 JavaScript TypeScript 题解。 Leetcode's answers by JavaScript and TypeScript. easy 66.加一 (Plus One) 67.二进制求和 (Add Binary) 69.x 的平方根 (Sqrt(x)) 70.爬楼梯 ...