題目敘述 Triangle

題目會給我們一個三角形的二維陣列triangle ，每個元素分別代表每個格子的成本，請問我們從最頂端到底部的下墜路徑的最小成本總和是多少?

每次下墜到下一排的時候，可以有兩種選擇:

1.往左下方的格子點移動。

2.往右下方的格子點移動。


測試範例

Examp

學習

職場

以行動支持創作者！付費即可解鎖

軟體開發

由有業界實戰經驗的演算法工程師，
手把手教你建立解題的框架，
一步步寫出高效、清晰易懂的解題答案。
著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。
深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。
在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。

小松鼠的演算法樂園

用格子點DP來解 三角形最小成本下降路徑 Triangle_Leetcode #120

Minimum Path Sum

給定一個矩陣，每個格子點代表經過的對應成本。
每回合可以往右移動一格或往下移動一格。

請問從起點左上角 走到 終點右下角的最小路徑成本總和是多少?



投資理財

用DP框架來思考 Minimum Path Sum 最小路徑成本總和_Leetcode #64

這篇文章，會帶著大家複習以前學過的 格子點DP框架，
並且以最小成本的下降路徑的應用題與概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。

最小成本下降路徑的形式

每個格子點的值代表經過的成本。

要求從最上面那排往下方走，落到最下一排的最小成本的下降路徑。




合縱連橫: 從 格子點DP框架 理解 最小成本的下降路徑

這題基本上是前一題巴斯卡三角形的孿生題，那題和這題的本質是完全一樣的，只是題目要求稍有不同。

前一題求的是整個巴斯卡三角形，這一題求的是巴斯卡三角形的最後一層。


職場產業

DP動態規劃 深入淺出 以Pascal's Triangle II 巴斯卡三角形 II為例

上次學過2D DP入門題目 Unique Path，接著來看進階一點的高度關聯延伸題
Unique Path II，這次板子上多了障礙物。
題目給定我們一個棋盤的高與寬，起點固定在左上角，終點固定在右下角。
每一步只能選擇往右走一格，或者往下走一格，不能回頭。
有障礙物的格子無法通過。

DP動態規劃 深入淺出 以Unique Path II 路徑總數II 為例

題目會給定我們一個三角形排列的香檳塔，第一層有一杯酒杯，第二層有兩杯酒杯，...，第k層有k杯酒杯，依此類推。
假如上一層的酒杯已經倒滿杯，多出來的部分會向下一層流動，並且均分一半給下一層最靠近的兩杯酒杯。
假如在最上層第一杯開始注入香檳，初始量為參數pour，最後第i層的第j杯會有多少香檳在裡面?