Re: [偷可] 規劃小松鼠

[cuteSquirrel (可愛的小松鼠)]

今天額外多想到的 做個紀錄

背後使用到同樣觀念的思考邏輯與框架

子集合

Subsets


組合(不考慮順序)

Coin Change II

Combination Sum

可以從Subsets 衍生得到 Combinations


排列(順序有關係)

從Coin Change II 變化而來 Combination Sum IV

Permutations

Phone Number


※ 引述《cuteSquirrel (可愛的小松鼠)》之銘言：

爬樓梯

費氏數列

泰伯納西數列

好字串

思考觀察共通點，看穿背後同樣的結構。

引入直觀法，觀察重複計算的成本

引入記憶化搜索，記住答案，避免重複計算。

其實就是trade-off, 用空間換取時間的進步。

———-

路徑總數 1 2 3

棋盤格子點走法的共同點

————

找零錢 1 2

子集合帶有targetSum

最精簡平方數化簡

引入bfs在等權團中有最短路徑的性質

解數字轉盤鎖最少撥動次數

————

博弈論 +minMax optimizations

石頭遊戲 1 2 3....整個系列

引入dfs+回朔法模板

枚舉/決策樹

子集合、組合數、直線排列

決勝21點



—————

交易模擬

最佳股票買賣全系列

DP + StateMachine

——————

區間DP

打家劫舍全系列

最大子陣列

射氣球（反向思考，從最後一支弓箭去想）

切木條的最小成本

Range Sum

Integral Image

Submatrix, Subtectangle

最長遞增子序列

等差數列，等比數列


——————

樹型DP

Path sum

DFS + Tree traversal

———————-

字串DP

回文子字串/子序列

正規表示式配對

編輯距離

最長共同子序列


-----
Sent from JPTT on my iPhone

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.206.247 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/talk/M.1710516576.A.30B.html
→ TKB5566: 演算法小松鼠
→ TKB5566: 資料結構小松鼠
→ TKB5566: Algo小松鼠
→ cuteSquirrel: 厲害 全部答對
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.206.247 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/talk/M.1710684966.A.2A4.html
推 Lyu7: 今天的題目是射氣球！