三角形最小路徑和

題目描述：給定一個三角形 triangle ，找出自頂向下的最小路徑和。

每一步只能移動到下一行中相鄰的結(jié)點(diǎn)上。相鄰的結(jié)點(diǎn) 在這里指的是 下標(biāo) 與 上一層結(jié)點(diǎn)下標(biāo) 相同或者等于 上一層結(jié)點(diǎn)下標(biāo) + 1 的兩個結(jié)點(diǎn)。也就是說，如果正位于當(dāng)前行的下標(biāo) i ，那么下一步可以移動到下一行的下標(biāo) i 或 i + 1 。

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/triangle/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：動態(tài)規(guī)劃

使用一個數(shù)組記錄到達(dá)每一層的結(jié)點(diǎn)的最小的路徑和，然后動態(tài)規(guī)劃的過程有以下依據(jù)：

• 每一層的第一個結(jié)點(diǎn)只能由上一層的第一個結(jié)點(diǎn)到達(dá)；

• 每一層的第 2 ~ size-1 個結(jié)點(diǎn)，可以由上一層相同位置或者上一個位置到達(dá)，取其中的較小值；

• 每一層的最后一個結(jié)點(diǎn)只能由上一層的最后一個節(jié)點(diǎn)到達(dá)。

最后，返回到達(dá)最后一層結(jié)點(diǎn)的最小路徑和。

【每日寄語】 你就把現(xiàn)在的辛苦，看成一種投資，是對未來的投資，你以后才會有舒舒服服的自由。