題目敘述 Binary Tree Maximum Path Sum

給定一個二元樹，請找出最大的區間路徑和是多少?

註:
區間路徑和 = 某個節點a -> 某個節點b的路徑節點值總和。



學習

職場

投資理財

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

軟體開發

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

小松鼠的演算法樂園

用樹型DP思想來看 二元樹最大的區間路徑和 Binary Tree Max Path Sum_Leetcode #124

題目敘述 Combination Sum IV
給定一個輸入陣列nums，和目標值target，從nums裡面挑數字去湊出總和 = target，數字可以重複挑選。

請問有多少排列數可以湊出target？

註: 排列數的意思就是位置不同代表兩種不同的方法數。



化簡無所不在 用找零錢DP框架來解 組合數之和IV_Combinations Sum IV_Leetcode #377

Minimum Path Sum

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

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



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

給定一個輸入陣列，計算最長遞增子序列的總數。本題和Longest Common Subsequence相似，需要設定一個計數器，記錄最長遞增子序列的數量。透過DP模型的化簡方式來解決問題。時間複雜度為O(n^2)，空間複雜度為O(n)。主要使用回頭看的技巧，找出比較小的元素去延伸遞增子序列的長度。

文化生活

化簡無所不在 用LIS的DP模型解Num of Longest Increasing Subseq._LC#673

題目會給我們一個nums陣列，分別代表每棟房屋的價值，也就是房屋內有的現金數量。
題目敘述給的情境是假想盜賊要偷東西，限制是相鄰的兩棟房屋不能一起偷，只能選擇其中一棟，否則就會觸發警報器。第一棟和最後一棟也被視為相鄰。

請問怎麼選擇哪幾棟房屋下手，可以

化簡無所不在 用學過的DP模型解House Robbery II_Leetcode #213

DP特訓班的分類目錄
與 推薦的學習、練習順序

親子與教育

DP演算法框架 與 推薦的DP學習路徑 (持續更新中)

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

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


職場產業

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

今天再來看一題入門的2D DP題目: 巴斯卡三角形

再次複習Dynamic programming的解題框架，可分為三大步驟
1.定義狀態 [我在哪裡]
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
3. 釐清初始狀態(也可以說是遞