triangle

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

Given a <code>triangle</code> array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index <code>i</code> on the current row, you may move to either index <code>i</code> or index <code>i + 1</code> on the next row.

&nbsp;
Example 1:

<pre>
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
 2
 3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
</pre>

Example 2:

<pre>
Input: triangle = [[-10]]
Output: -10
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= triangle.length &lt;= 200</code></li>
	<li><code>triangle[0].length == 1</code></li>
	<li><code>triangle[i].length == triangle[i - 1].length + 1</code></li>
	<li><code>-104 &lt;= triangle[i][j] &lt;= 104</code></li>
</ul>

&nbsp;
Follow up: Could you&nbsp;do this using only <code>O(n)</code> extra space, where <code>n</code> is the total number of rows in the triangle?

minimumTotal

Triangle

Array

Dynamic Programming

&#32473;&#23450;&#19968;&#20010;&#19977;&#35282;&#24418; <code>triangle</code> &#65292;&#25214;&#20986;&#33258;&#39030;&#21521;&#19979;&#30340;&#26368;&#23567;&#36335;&#24452;&#21644;&#12290;

&#27599;&#19968;&#27493;&#21482;&#33021;&#31227;&#21160;&#21040;&#19979;&#19968;&#34892;&#20013;&#30456;&#37051;&#30340;&#32467;&#28857;&#19978;&#12290;&#30456;&#37051;&#30340;&#32467;&#28857; &#22312;&#36825;&#37324;&#25351;&#30340;&#26159; &#19979;&#26631; &#19982; &#19978;&#19968;&#23618;&#32467;&#28857;&#19979;&#26631; &#30456;&#21516;&#25110;&#32773;&#31561;&#20110; &#19978;&#19968;&#23618;&#32467;&#28857;&#19979;&#26631; + 1 &#30340;&#20004;&#20010;&#32467;&#28857;&#12290;&#20063;&#23601;&#26159;&#35828;&#65292;&#22914;&#26524;&#27491;&#20301;&#20110;&#24403;&#21069;&#34892;&#30340;&#19979;&#26631; <code>i</code> &#65292;&#37027;&#20040;&#19979;&#19968;&#27493;&#21487;&#20197;&#31227;&#21160;&#21040;&#19979;&#19968;&#34892;&#30340;&#19979;&#26631; <code>i</code> &#25110; <code>i + 1</code> &#12290;

&nbsp;

&#31034;&#20363; 1&#65306;

<pre>
&#36755;&#20837;&#65306;triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
&#36755;&#20986;&#65306;11
&#35299;&#37322;&#65306;&#22914;&#19979;&#38754;&#31616;&#22270;&#25152;&#31034;&#65306;
 2
 3 4
 6 5 7
4 1 8 3
&#33258;&#39030;&#21521;&#19979;&#30340;&#26368;&#23567;&#36335;&#24452;&#21644;&#20026;&nbsp;11&#65288;&#21363;&#65292;2&nbsp;+&nbsp;3&nbsp;+&nbsp;5&nbsp;+&nbsp;1&nbsp;= 11&#65289;&#12290;
</pre>

&#31034;&#20363; 2&#65306;

<pre>
&#36755;&#20837;&#65306;triangle = [[-10]]
&#36755;&#20986;&#65306;-10
</pre>

&nbsp;

&#25552;&#31034;&#65306;

<ul>
	<li><code>1 <= triangle.length <= 200</code></li>
	<li><code>triangle[0].length == 1</code></li>
	<li><code>triangle[i].length == triangle[i - 1].length + 1</code></li>
	<li><code>-104 <= triangle[i][j] <= 104</code></li>
</ul>

&nbsp;

&#36827;&#38454;&#65306;

<ul>
	<li>&#20320;&#21487;&#20197;&#21482;&#20351;&#29992; <code>O(n)</code>&nbsp;&#30340;&#39069;&#22806;&#31354;&#38388;&#65288;<code>n</code> &#20026;&#19977;&#35282;&#24418;&#30340;&#24635;&#34892;&#25968;&#65289;&#26469;&#35299;&#20915;&#36825;&#20010;&#38382;&#39064;&#21527;&#65311;</li>
</ul>

Sunbelt Computer Software

PL/B Language Development and Support