LeetCode-120-三角形最小路徑和
三角形最小路徑和
題目描述：給定一個三角形 triangle ，找出自頂向下的最小路徑和。
每一步只能移動到下一行中相鄰的結點上。相鄰的結點 在這裡指的是 下標 與 上一層結點下標 相同或者等於 上一層結點下標 + 1 的兩個結點。也就是說，如果正位於當前行的下標 i ，那麼下一步可以移動到下一行的下標 i 或 i + 1 。
示例說明請見LeetCode官網。
連結：
https：//
leetcode-cn。com/problem
s/triangle/
著作權歸領釦網路所有。商業轉載請聯絡官方授權，非商業轉載請註明出處。
解法一：動態規劃
使用一個數組記錄到達每一層的結點的最小的路徑和，然後動態規劃的過程有以下依據：
每一層的第一個結點只能由上一層的第一個結點到達；
每一層的第 2 ~ size-1 個結點，可以由上一層相同位置或者上一個位置到達，取其中的較小值；
每一層的最後一個結點只能由上一層的最後一個節點到達。
最後，返回到達最後一層結點的最小路徑和。
import
java。util。ArrayList
；
import
java。util。Arrays
；
import
java。util。List
；
public
class
LeetCode_120
{
/**
* 動態規劃
*
* @param triangle
* @return
*/
public
static
int
minimumTotal
（
List
<
List
<
Integer
>>
triangle
）
{
// 記錄到達每一層的每一個結點的路徑和，初始化都是0
int
［］
result
=
new
int
［
triangle
。
size
（）］；
for
（
List
<
Integer
>
integers
：
triangle
）
{
// 記錄到達當前層每一個結點的路徑和，初始化都是0
int
［］
cur
=
new
int
［
triangle
。
size
（）］；
// 每一層的第一個結點只能由上一層的第一個結點到達
cur
［
0
］
=
result
［
0
］
+
integers
。
get
（
0
）；
int
index
；
for
（
index
=
1
；
index
<
integers
。
size
（）
-
1
；
index
++）
{
// 每一層的第 2 ~ size-1 個結點，可以有上一層相同位置或者上一個位置到達，取其中的較小值
cur
［
index
］
=
integers
。
get
（
index
）
+
Math
。
min
（
result
［
index
-
1
］，
result
［
index
］）；
}
if
（
index
<
integers
。
size
（））
{
// 每一層的最後一個結點只能由上一層的最後一個節點到達
cur
［
index
］
=
integers
。
get
（
index
）
+
result
［
index
-
1
］；
}
result
=
cur
；
}
// 最後，返回到達最後一層的最小的路徑和的值
return
Arrays
。
stream
（
result
）。
min
（）。
getAsInt
（）；
}
public
static
void
main
（
String
［］
args
）
{
List
<
List
<
Integer
>>
triangle
=
new
ArrayList
<>（）；
List
<
Integer
>
one
=
new
ArrayList
<>（）；
one
。
add
（
2
）；
triangle
。
add
（
one
）；
List
<
Integer
>
two
=
new
ArrayList
<>（）；
two
。
add
（
3
）；
two
。
add
（
4
）；
triangle
。
add
（
two
）；
List
<
Integer
>
three
=
new
ArrayList
<>（）；
three
。
add
（
6
）；
three
。
add
（
5
）；
three
。
add
（
7
）；
triangle
。
add
（
three
）；
List
<
Integer
>
four
=
new
ArrayList
<>（）；
four
。
add
（
4
）；
four
。
add
（
1
）；
four
。
add
（
8
）；
four
。
add
（
3
）；
triangle
。
add
（
four
）；
System
。
out
。
println
（
minimumTotal
（
triangle
））；
}
}
【每日寄語】
你就把現在的辛苦，看成一種投資，是對未來的投資，你以後才會有舒舒服服的自由。
